Finite-size corrections in the random assignment problem

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...

Full description

Saved in:
Bibliographic Details
Published in:Physical review. E 2017-05, Vol.95 (5-1), p.052129-052129, Article 052129
Main Authors: Caracciolo, Sergio, D'Achille, Matteo P, Malatesta, Enrico M, Sicuro, Gabriele
Format: Article
Language:English
Subjects:
Mathematics
Physics
Probability
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:2470-0045
2470-0053
DOI:10.1103/PhysRevE.95.052129