We investigate the average minimum cost of a bipartite matching between two samples
of
independent random points uniformly distributed on a unit cube in
dimensions, where the matching cost between two points is given by any power
of their Euclidean
distance. As
grows, we prove convergence, after a suitable renormalization, towards a finite and
positive constant. We also consider the analogous problem of optimal transport between
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
matching problem, optimal transport, geometric probability