Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

On the quadratic random matching problem in two-dimensional domains

Abstract : We investigate the average minimum cost of a bipartite matching, with respect to the squared Euclidean distance, between two samples of n i.i.d. random points on a bounded Lipschitz domain in the Euclidean plane, whose common law is absolutely continuous with strictly positive Hölder continuous density. We confirm in particular the validity of a conjecture by D. Benedetto and E. Caglioti stating that the asymptotic cost as n grows is given by the logarithm of n multiplied by an explicit constant times the volume of the domain. Our proof relies on a reduction to the optimal transport problem between the associated empirical measures and a Whitney-type decomposition of the domain, together with suitable upper and lower bounds for local and global contributions, both ultimately based on PDE tools. We further show how to extend our results to more general settings, including Riemannian manifolds, and also give an application to the asymptotic cost of the random quadratic bipartite travelling salesperson problem.
Document type :
Preprints, Working Papers, ...
Complete list of metadata
Contributor : Michael Goldman Connect in order to contact the contributor
Submitted on : Wednesday, October 27, 2021 - 10:42:18 AM
Last modification on : Tuesday, November 16, 2021 - 4:03:09 AM


Files produced by the author(s)


  • HAL Id : hal-03405272, version 1
  • ARXIV : 2110.14372


Luigi Ambrosio, Michael Goldman, Dario Trevisan. On the quadratic random matching problem in two-dimensional domains. 2021. ⟨hal-03405272⟩



Record views


Files downloads