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\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 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.

Keywords

Mathematical Subject Classification

Milestones

Authors