Quadratic stochastic Euclidean bipartite matching problem

Abstract

We propose a new approach for the study of the quadratic stochastic Euclidean bipartite matching problem between two sets of $N$ points each, $N\gg 1$. The points are supposed independently randomly generated on a domain $\Omega \subset {\mathbb{R}}^d$ with a given distribution $\rho (\mathbf{x})$ on $\Omega$. In particular, we derive a general expression for the correlation function and for the average optimal cost of the optimal matching. A previous ansatz for the matching problem on the flat hypertorus is obtained as particular case.

5 pages + Supplemental material

References in corpus (4)

• Scaling hypothesis for the Euclidean bipartite matching problem
• Scaling hypothesis for the Euclidean bipartite matching problem II. Correlation functions
• On the one dimensional Euclidean matching problem: exact solutions, correlation functions and universality
• Correlation function for the Grid-Poisson Euclidean matching on a line and on a circle

Cited by in corpus (17)

• Euclidean random matching in 2D for non-constant densities
• 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
• Random assignment problems on $2d$ manifolds
• Anomalous scaling of the optimal cost in the one-dimensional random assignment problem
• Criticality and conformality in the random dimer model
• Random-link matching problems on random regular graphs
• Selberg integrals in 1D random Euclidean optimization problems
• Plastic number and possible optimal solutions for an Euclidean 2-matching in one dimension
• The Random Fractional Matching Problem
• Average optimal cost for the Euclidean TSP in one dimension
• The p-Airy distribution
• The Most Dispersed Subset of Random Points in ${\mathbb{R}}^d$