PreprintarXiv licencearXiv
Exact Asymptotics for the 2D Euclidean Random Matching Problem
Abstract
We determine the exact first-order asymptotics of the expected optimal cost in two-dimensional random bipartite matching, for every finite power cost q ≥ 1, on the flat torus. In the endpoint case q=1, this answers a question by Talagrand, in the periodic case. The argument involves the closely related asymptotics of the energy of the solution of the p-Poisson equation with a regularized white-noise source. In the limit of vanishing regularization parameter, we identify this energy as the solution of a Variational Martingale Problem on a limiting Gaussian filtration, whose value is characterized by a parabolic Monge-Ampère flow.
Related
- Exact cost of the Euclidean Maximum Traveling Salesman Problem in one dimension
- Exact Second-Order Asymptotics for the Gaussian Gray--Wyner Problem
- Exact Second-Order Asymptotics for the Discrete Wyner--Ziv Problem
- Exact Second-Order Asymptotics for the Wyner--Ahlswede--Körner Problem
- Variance Bounds for Minimum Perfect Matching Problem by Random Walk on Multinomial Distribution
BibTeX
@misc{armegioiu2026exact,
title = {{Exact Asymptotics for the 2D Euclidean Random Matching Problem}},
author = {Victor Armegioiu and Michael Goldman and Francesco Grotto and Dario Trevisan},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2609.08717},
eprint = {2609.08717},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.08717},
}
RIS
TY - UNPB
TI - Exact Asymptotics for the 2D Euclidean Random Matching Problem
AU - Victor Armegioiu
AU - Michael Goldman
AU - Francesco Grotto
AU - Dario Trevisan
PY - 2026
DA - 2026/10/11
PB - arXiv
DO - 10.48550/arxiv.2609.08717
UR - https://arxiv.org/abs/2609.08717
AB - We determine the exact first-order asymptotics of the expected optimal cost in two-dimensional random bipartite matching, for every finite power cost q ≥ 1, on the flat torus. In the endpoint case q=1, this answers a question by Talagrand, in the periodic case. The argument involves the closely related asymptotics of the energy of the solution of the p-Poisson equation with a regularized white-noise source. In the limit of vanishing regularization parameter, we identify this energy as the solution of a Variational Martingale Problem on a limiting Gaussian filtration, whose value is characterized by a parabolic Monge-Ampère flow.
ER -