UC Berkeley

The random assignment (or bipartite matching) problem asks about An = minπ ∑ni=1 c(i, π(i)) where (c(i, j)) is a n × n matrix with i.i.d. entries, say with exponential(1) distribution, and the minimum is over permutations π. Mézard and Parisi (1987) used the replica method from statistical physics to argue nonrigorously that EAn → ζ(2) = π2/6. Aldous (1992) identified the limit in terms of a matching problem on a limit infinite tree. Here we construct the optimal matching on the infinite tree. This yields a rigorous proof of the ζ(2) limit and of the conjectured limit distribution of 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. © 2001 John Wiley & Sons, Inc. Random Struct. Alg., 18, 381-418, 2001.