We investigate the minimum cost of a wide class of combinatorial optimization problems over random bipartite geometric graphs in Rd where the edge cost between two points is given by a p-th power of their Euclidean distance. This includes e.g.\ the travelling salesperson problem and the bounded degree minimum spanning tree. We establish in particular almost sure convergence, as n grows, of a suitable renormalization of the random minimum cost, if the points are uniformly distributed and d≥3, 1≤p
Optimal transport methods for combinatorial optimization over two random point sets
Goldman M.;Trevisan D.
2024-01-01
Abstract
We investigate the minimum cost of a wide class of combinatorial optimization problems over random bipartite geometric graphs in Rd where the edge cost between two points is given by a p-th power of their Euclidean distance. This includes e.g.\ the travelling salesperson problem and the bounded degree minimum spanning tree. We establish in particular almost sure convergence, as n grows, of a suitable renormalization of the random minimum cost, if the points are uniformly distributed and d≥3, 1≤pFile in questo prodotto:
Non ci sono file associati a questo prodotto.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
