The ζ(2) limit in the random assignment problem

The random assignment (or bipartite matching) problem asks about A, min(pi) Sigma (n)(i=1) c(i, pi (i)), where (c(i, j)) is a n x n matrix with i.i.d. entries, say with exponential(1) distribution, and the minimum is over permutations pi. Mezard and Parisi (1987) used the replica method from statistical physics to argue nonrigorously that EA(n) --> zeta (2) = pi (2)/6. Aldous (1992) identified the limit in terms of a matching problem on a limit infinite tree. Herl 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 od edge-costs and their rank-orders in the optimal matching. It also yields the asymptotic essential uniqueness property: every almost-optimal matching coincides with the optimal matching except on a small proportion of edges. (C) 2001 John Wiley & Sons, Inc.