Combinatorial optimization over two random point sets

2011/03/14 by Franck Barthe, Barthe, Franck, Charles Bordenave +1 · 1 citation
Mathematics · #FOS: Mathematics #Probability (math.PR) #math.PR

paper · pdf · doi:10.48550/arxiv.1103.2734

34 pages

arxiv created 2011/10/05 · arxiv updated 2011/10/06

Abstract

We analyze combinatorial optimization problems over a pair of random point sets of equal cardinal. Typical examples include the matching of minimal length, the traveling salesperson tour constrained to alternate between points of each set, or the connected bipartite r-regular graph of minimal length. As the cardinal of the sets goes to infinity, we investigate the convergence of such bipartite functionals.

Cited by

• Convergence of empirical Gromov-Wasserstein distance

Related

• Optimal transport methods for combinatorial optimization over two random point sets
• Limit theory of combinatorial optimization for random geometric graphs
• Revisiting Random Points: Combinatorial Complexity and Algorithms
• Approximating the Expected Values for Combinatorial Optimization Problems over Stochastic Points
• Central limit theorems for combinatorial optimization problems on sparse Erdős-Rényi graphs