The zeta(2) limit in the random assignment problem

Simple item page
dc.creatorAldous, David J.
dc.date2000-10-06
dc.date.accessioned2026-07-07T04:37:52Z
dc.date.available2026-07-07T04:37:52Z
dc.descriptionThe 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.
dc.description45 pages
dc.identifierhttps://arxiv.org/abs/math/0010063
dc.identifierhttp://arxiv.org/abs/math/0010063
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/60068
dc.subjectProbability
dc.subjectMathematical Physics
dc.subject60C05, 82B44
dc.titleThe zeta(2) limit in the random assignment problem
dc.typetext

Files

Collections

arXiv