Skip to main navigation Skip to search Skip to main content

On the quadratic random matching problem in two-dimensional domains

  • Scuola Normale Superiore di Pisa
  • Laboratoire de Probabilités et Modèles Aléatoires
  • University of Pisa

Research output: Contribution to journal › Article › peer-review

13 Citations (Scopus)

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.

Original languageEnglish
Article number54
JournalElectronic Journal of Probability
Volume27
DOIs
Publication statusPublished - 1 Jan 2022
Externally publishedYes

Keywords

  • geometric probability
  • matching problem
  • optimal transport

Fingerprint

Dive into the research topics of 'On the quadratic random matching problem in two-dimensional domains'. Together they form a unique fingerprint.

Cite this