Enrico Maria Malatesta — Università di Milano #
Finite-size corrections in the random assignment problem #
The assignment problem is a long standing problem in combinatorial optimization which consists in finding the perfect matching between two sets of $N$ points that minimizes the total length. In the random assignment, the costs for all the ​possible pairs to be matched are independent random variables identically distributed​ according to a distribution law $\rho(w)$​. Among the many great successes of the replica formalism there is the derivation of the exact value of the average density cost for the random assignment. It is well known that, in the limit of an infinite number of possible pairs, the average optimal cost depends only on the behavior of the disorder distribution near lowest possible pair cost. Here we present how the choice of the disorder distribution affects the finite size corrections to the average cost. We have found that corrections are smaller in the case of a pure power law probability distribution, i.e. $\rho(w) \sim w^r$. In this case, only analytical corrections are present, that is in inverse powers of the number of points. On the contrary, and interestingly enough, the exponent of the leading correction changes as a function of $r$ whenever $\rho(w) \sim w^r (\eta_0 + \eta_1 \, w + \dots )$ with $\eta_1\neq 0$. We believe that this is the first example in which the effects of the choice of the distribution law for disorder has been fully taken into account.

References: [1] S. Caracciolo, M.P. D’Achille, E.M. Malatesta, G. Sicuro, Finite size corrections in the random assignment problem, Physical Review E 95, 052129, 2017.