Finite-size corrections in the random assignment problem

Abstract

We analytically derive, in the context of the replica formalism, the first finite size corrections to the average optimal cost in the random assignment problem for a quite generic distribution law for the costs. We show that, when moving from a power-law distribution to a $\Gamma$ distribution, the leading correction changes both in sign and in its scaling properties. We also examine the behavior of the corrections when approaching a $\delta$-function distribution. By using a numerical solution of the saddle-point equations, we provide predictions that are confirmed by numerical simulations.

arXiv comment16 pages, 4 figures

References in corpus (10)

• The Quantum Adiabatic Algorithm applied to random optimization problems: the quantum spin glass perspective
• 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
• Neighborhood preferences in random matching problems
• One-loop diagrams in the Random Euclidean Matching Problem

Cited by in corpus (6)

• Random Euclidean matching problems in one dimension
• The Dyck bound in the concave 1-dimensional random assignment model
• Fluctuations in the random-link matching problem
• Criticality and conformality in the random dimer model
• The number of optimal matchings for Euclidean Assignment on the line
• Average optimal cost for the Euclidean TSP in one dimension