Calculus of Variations and Geometric Measure Theory

M. Goldman - D. Trevisan

Convergence of asymptotic costs for random Euclidean matching problems

created by goldman on 10 Sep 2020
modified by trevisan on 05 Jul 2024


Accepted Paper

Inserted: 10 sep 2020
Last Updated: 5 jul 2024

Journal: Probability and Mathematical Physics
Year: 2020

ArXiv: 2009.04128 PDF


We investigate the average minimum cost of a bipartite matching between two samples of n independent random points uniformly distributed on a unit cube in d $\ge$ 3 dimensions, where the matching cost between two points is given by any power p $\ge$ 1 of their Euclidean distance. As n grows, we prove convergence, after a suitable renormalization, towards a finite and positive constant. We also consider the analogous problem of optimal transport between n points and the uniform measure. The proofs combine sub-additivity inequalities with a PDE ansatz similar to the one proposed in the context of the matching problem in two dimensions and later extended to obtain upper bounds in higher dimensions.