Almost sure convergence of the minimum bipartite matching functional in Euclidean space

2002/05/13 by J. H. Boutet de Monvel, O. C. Martin · 1 citation
Mathematics · #math.CO #math.OC #math.PR #msc:F.2.2 #msc:G.3

paper · pdf

published as Combinatorica 22(4):523-530 (2002) · To appear in Combinatorica

arxiv created 2002/05/13 · arxiv updated 2009/11/30

Abstract

Let L_N = L_MBM(X₁,..., X_N; Y₁,..., Y_N) be the minimum length of a bipartite matching between two sets of points in R^d, where X₁,..., X_N,... and Y₁,..., Y_N,... are random points independently and uniformly distributed in [0,1]^d. We prove that for d ≥ 3, L_N/N^1-1/d converges with probability one to a constant β_MBM(d)>0 as N→ ∞ .

Cited by

• Convergence of empirical Gromov-Wasserstein distance

Related

• A Conjecture on random bipartite matching
• On the quadratic random matching problem in two-dimensional domains
• Average Distance of Random Bipartite Matching in One-dimensional Space and Networks
• Combinatorial optimization over two random point sets
• Expected Optimal Distances of Random Bipartite Matching in D-dimensional Spaces: Approximate Formulas and Applications to Mobility Services