Anomalous scaling of the optimal cost in the one-dimensional random assignment problem

Abstract

We consider the random Euclidean assignment problem on the line between two sets of $N$ random points, independently generated with the same probability density function $\varrho$. The cost of the matching is supposed to be dependent on a power $p>1$ of the Euclidean distance of the matched pairs. We discuss an integral expression for the average optimal cost for $N\gg 1$ that generalizes a previous result obtained for $p=2$. We also study the possible divergence of the given expression due to the vanishing of the probability density function. The provided regularization recipe allows us to recover the proper scaling law for the cost in the divergent cases, and possibly some of the involved coefficients. The possibility that the support of $\varrho$ is a disconnected interval is also analysed. We exemplify the proposed procedure and we compare our predictions with the results of numerical simulations.

arXiv comment18 pages, 12 figures

References in corpus (11)

• Scaling hypothesis for the Euclidean bipartite matching problem
• Scaling hypothesis for the Euclidean bipartite matching problem II. Correlation functions
• Comparing Mean Field and Euclidean Matching Problems
• 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
• 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
• Plastic number and possible optimal solutions for an Euclidean 2-matching in one dimension

Cited by in corpus (3)

• Euclidean random matching in 2D for non-constant densities
• The Dyck bound in the concave 1-dimensional random assignment model
• The number of optimal matchings for Euclidean Assignment on the line