The zeta(2) limit in the random assignment problem

2000/10/06 by David J. Aldous, Aldous, David J. · 1 citation
Mathematics · Physics and Astronomy · #60C05 #82B44 #FOS: Mathematics #FOS: Physical sciences #Mathematical Physics (math-ph) #Probability (math.PR) #math-ph #math.MP #math.PR #msc:60C05 #msc:82B44

paper · pdf · doi:10.48550/arxiv.math/0010063

45 pages

arxiv created 2000/10/06 · arxiv updated 2009/11/30

Abstract

The random assignment (or bipartite matching) problem studies the random total cost A_n of the optimal assignment of each of n jobs to each of n machines, where the costs of the n² possible job-machine matches has exponential (mean 1) distribution. Mezard - Parisi (1987) used the replica method from statistical physics to argue non-rigorously that EA_n converges to zeta(2) = pi²/6. Aldous (1992) identified the limit as the optimal solution of a matching problem on an infinite tree. Continuing that approach, we construct the optimal matching on the infinite tree. This yields a rigorous proof of the zeta(2) limit and of the conjectured limit distribution of edge-costs and their rank-orders in the optimal matching.

Cited by

• A CLuP algorithm to practically achieve ∼ 0.76 SK--model ground state free energy

Related

• Towards the distribution of the smallest matching in the Random Assignment Problem
• Belief propagation : an asymptotically optimal algorithm for the random assignment problem
• A proof of a conjecture of Buck, Chan and Robbins on the random assignment problem
• A Proof of Parisi's Conjecture on the Random Assignment Problem
• A Generalization of the Random Assignment Problem