PreprintCC BY 4.0HAL
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{goldman2026exact,
title = {{Exact Asymptotics for the 2D Euclidean Random Matching Problem}},
author = {Michael Goldman and Victor Armegioiu and Francesco Grotto and Dario Trevisan},
howpublished = {HAL},
year = {2026},
month = oct,
url = {https://hal.science/hal-05784892v1},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Exact Asymptotics for the 2D Euclidean Random Matching Problem
AU - Michael Goldman
AU - Victor Armegioiu
AU - Francesco Grotto
AU - Dario Trevisan
PY - 2026
DA - 2026/10/07
PB - HAL
UR - https://hal.science/hal-05784892v1
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 -