Finite-size corrections in the random assignment problem

2017/02/28 by Sergio Caracciolo, Matteo d'Achille, Matteo P. D'Achille +2
Mathematics · Physics and Astronomy · #Applied mathematics #Complex Network Analysis Techniques #Distribution (mathematics) #Distribution function #Formalism (music) #Geometry #Mathematical analysis #Mathematical optimization #Mathematics #Opinion Dynamics and Social Influence #Physics #Power law #Quantum mechanics #Random variable #Replica #Saddle #Saddle point #Scaling #Scaling law #Statistical physics #Statistics #Theoretical and Computational Physics #cond-mat.dis-nn

paper · pdf · doi:10.1103/physreve.95.052129

published as Phys. Rev. E 95, 052129 (2017) · 16 pages, 4 figures

arxiv created 2017/05/17 · openalex publication_date 2017/05/17 · arxiv updated 2017/05/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05

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 Γ distribution, the leading correction changes both in sign and in its scaling properties. We also examine the behavior of the corrections when approaching a δ-function distribution. By using a numerical solution of the saddle-point equations, we provide predictions that are confirmed by numerical simulations.

Citations

• Correlation function for the Grid-Poisson Euclidean matching on a line and on a circle
• Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
• The Hungarian method for the assignment problem
• One-loop diagrams in the random Euclidean matching problem
• Fractional Differential Equations
• Paths, Trees, and Flowers