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≥3 dimensions, where the matching cost between two points is given by any power p≥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 subadditivity 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.

Convergence of asymptotic costs for random Euclidean matching problems

Dario Trevisan
2021-01-01

Abstract

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≥3 dimensions, where the matching cost between two points is given by any power p≥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 subadditivity 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.
2021
Goldman, Michael; Trevisan, Dario
File in questo prodotto:
File Dimensione Formato  
Goldman_Trevisan.pdf

accesso aperto

Descrizione: Accepted manuscript from Arxiv
Tipologia: Documento in Post-print
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 282.15 kB
Formato Adobe PDF
282.15 kB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11568/1118605
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 4
  • ???jsp.display-item.citation.isi??? ND
social impact