The zeta(2) limit in the random assignment problem
Preprint
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^2 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^2/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.Keywords
All Related Versions
This publication has 18 references indexed in Scilit:
- On the expected value of the minimum assignmentRandom Structures & Algorithms, 2002
- Exact Expectations and Distributions for the Random Assignment ProblemCombinatorics, Probability and Computing, 2002
- The percolation process on a tree where infinite clusters are frozenMathematical Proceedings of the Cambridge Philosophical Society, 2000
- Constructive bounds and exact expectations for the random assignment problemRandom Structures & Algorithms, 1999
- Comparing mean field and Euclidean matching problemsThe European Physical Journal B, 1998
- Certain expected values in the random assignment problemOperations Research Letters, 1993
- Asymptotics in the random assignment problemProbability Theory and Related Fields, 1992
- On linear programs with random costsMathematical Programming, 1986
- On the value of a random minimum spanning tree problemDiscrete Applied Mathematics, 1985
- The shortest path through many pointsMathematical Proceedings of the Cambridge Philosophical Society, 1959