Premium
The ζ(2) limit in the random assignment problem
Author(s) -
Aldous David J.
Publication year - 2001
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.1015
Subject(s) - limit (mathematics) , mathematics , combinatorics , matching (statistics) , bipartite graph , uniqueness , tree (set theory) , rank (graph theory) , discrete mathematics , distribution (mathematics) , random matrix , statistics , mathematical analysis , physics , eigenvalues and eigenvectors , quantum mechanics , graph
The random assignment (or bipartite matching) problem asks about A n =min π ∑ i =1 nc ( 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 EA n →ζ(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