Optimal transport methods for combinatorial optimization over two random point sets

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