Scaling hypothesis for the Euclidean bipartite matching problem

Abstract

We propose a simple yet very predictive form, based on a Poisson's equation, for the functional dependence of the cost from the density of points in the Euclidean bipartite matching problem. This leads, for quadratic costs, to the analytic prediction of the large $N$ limit of the average cost in dimension $d=1,2$ and of the subleading correction in higher dimension. A non-trivial scaling exponent, ${\gamma }_d=\frac{d-2}{d}$, which differs from the monopartite's one, is found for the subleading correction. We argue that the same scaling holds true for a generic cost exponent in dimension $d>2$.

11 pages

Cited by in corpus (29)

• Quantum optimal transport with quantum channels
• Scaling hypothesis for the Euclidean bipartite matching problem II. Correlation functions
• On the one dimensional Euclidean matching problem: exact solutions, correlation functions and universality
• Quadratic stochastic Euclidean bipartite matching problem
• Correlation function for the Grid-Poisson Euclidean matching on a line and on a circle
• Euclidean random matching in 2D for non-constant densities
• A large-scale regularity theory for the Monge-Ampere equation with rough data and application to the optimal matching problem
• Random Euclidean matching problems in one dimension
• Solution for a bipartite Euclidean traveling-salesman problem in one dimension
• One-loop diagrams in the Random Euclidean Matching Problem
• Finite-size corrections in the random assignment problem
• The Dyck bound in the concave 1-dimensional random assignment model
• Exact value for the average optimal cost of bipartite traveling-salesman and 2-factor problems in two dimensions
• Anomalous scaling of the optimal cost in the one-dimensional random assignment problem
• Random assignment problems on $2d$ manifolds
• An MBO scheme for minimizing the graph Ohta-Kawasaki functional
• Criticality and conformality in the random dimer model
• Empirical measures and random walks on compact spaces in the quadratic Wasserstein metric
• Random-link matching problems on random regular graphs
• Quantitative linearization results for the Monge-Ampère equation
• Selberg integrals in 1D random Euclidean optimization problems
• Plastic number and possible optimal solutions for an Euclidean 2-matching in one dimension
• Asymptotics of smoothed Wasserstein distances
• Convergence of asymptotic costs for random Euclidean matching problems
• Phase transition in the bipartite z-matching
• The p-Airy distribution
• Average optimal cost for the Euclidean TSP in one dimension
• Finer estimates on the 2-dimensional matching problem
• Some results on the optimal matching problem for the Jacobi model