Vol. 2, No. 2, 2021

Download this article
Download this article For screen
For printing
Recent Issues
Volume 5, Issue 1
Volume 4, Issue 4
Volume 4, Issue 3
Volume 4, Issue 2
Volume 4, Issue 1
Volume 3, Issue 4
Volume 3, Issue 3
Volume 3, Issue 2
Volume 3, Issue 1
Volume 2, Issue 4
Volume 2, Issue 3
Volume 2, Issue 2
Volume 2, Issue 1
Volume 1, Issue 1
The Journal
About the journal
Ethics and policies
Peer-review process
Submission guidelines
Submission form
Editorial board
ISSN (electronic): 2690-1005
ISSN (print): 2690-0998
Author Index
To Appear
Other MSP Journals
This article is available for purchase or by subscription. See below.
Convergence of asymptotic costs for random Euclidean matching problems

Michael Goldman and Dario Trevisan

Vol. 2 (2021), No. 2, 341–362

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.

PDF Access Denied

We have not been able to recognize your IP address as that of a subscriber to this journal.
Online access to the content of recent issues is by subscription, or purchase of single articles.

Please contact your institution's librarian suggesting a subscription, for example by using our journal-recom­mendation form. Or, visit our subscription page for instructions on purchasing a subscription.

You may also contact us at contact@msp.org
or by using our contact form.

Or, you may purchase this single article for USD 40.00:

matching problem, optimal transport, geometric probability
Mathematical Subject Classification
Primary: 35J05, 39B62, 60D05, 60F25, 90C05
Received: 15 September 2020
Accepted: 3 December 2020
Published: 22 May 2021
Michael Goldman
Laboratoire Jacques-Louis Lions
Université de Paris, CNRS
Dario Trevisan
Dipartimento di Matematica
Università di Pisa