Random Euclidean matching problems in one dimension

Abstract

We discuss the optimal matching solution for both the assignment problem and the matching problem in one dimension for a large class of convex cost functions. We consider the problem in a compact set with the topology both of the interval and of the circumference. Afterwards, we assume the points' positions to be random variables identically and independently distributed on the considered domain. We analytically obtain the average optimal cost in the asymptotic regime of very large number of points $N$ and some correlation functions for a power-law type cost function in the form $c(z)=z^p$, both in the $p>1$ case and in the $p<0$ case. The scaling of the optimal mean cost with the number of points is $N^{-\frac{p}{2}}$ for the assignment and $N^{-p}$ for the matching when $p>1$, whereas in both cases it is a constant when $p<0$. Finally, our predictions are compared with the results of numerical simulations.

21 pages

References in corpus (13)

• RNA Folding and Large N Matrix Theory
• Statistical mechanics of secondary structures formed by random RNA sequences
• Scaling hypothesis for the Euclidean bipartite matching problem
• Statistical Physics of RNA-folding
• Scaling hypothesis for the Euclidean bipartite matching problem II. Correlation functions
• Zero Temperature Properties of RNA Secondary Structures
• On the one dimensional Euclidean matching problem: exact solutions, correlation functions and universality
• On the finite size corrections to some random matching problems
• Quadratic stochastic Euclidean bipartite matching problem
• Correlation function for the Grid-Poisson Euclidean matching on a line and on a circle
• One-loop diagrams in the Random Euclidean Matching Problem
• Finite-size corrections in the random assignment problem
• Planar diagrams from optimization

Cited by in corpus (9)

• Solution for a bipartite Euclidean traveling-salesman problem in one dimension
• The Dyck bound in the concave 1-dimensional random assignment model
• Anomalous scaling of the optimal cost in the one-dimensional random assignment problem
• Criticality and conformality in the random dimer model
• Selberg integrals in 1D random Euclidean optimization problems
• Plastic number and possible optimal solutions for an Euclidean 2-matching in one dimension
• Average optimal cost for the Euclidean TSP in one dimension
• The number of optimal matchings for Euclidean Assignment on the line
• The Most Dispersed Subset of Random Points in ${\mathbb{R}}^d$