The DOI matches its Crossref record; 15 of the 15 references it cites were found in a registry or an index.
The ζ(2) limit in the random assignment problem
Abstract
The random assignment (or bipartite matching) problem asks about A n=min π ∑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 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
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Spin Glass Theory and Beyond: An Introduction to the Replica Method and Its Applications
Mezard, M., Parisi, G., & Virasoro, M. (1986) · World Scientific Lecture Notes in Physics · doi:10.1142/0271 · Cited by 3,653
Mezard, M., Parisi, G., Virasoro, M. A., & Thouless, D. J. (1988) · Physics Today · doi:10.1063/1.2811676 · Cited by 2,682
The shortest path through many points
Beardwood, J., Halton, J. H., & Hammersley, J. M. (1959) · Mathematical Proceedings of the Cambridge Philosophical Society · doi:10.1017/s0305004100034095 · Cited by 937
Encyclopedia of Statistical Sciences
KK, Kotz, S., Read, C., & Banks, D. (1998) · Journal of the American Statistical Association · doi:10.2307/2669895 · Cited by 587
Onk-connectivity for a geometric random graph
Penrose, M. D. (1999) · Random Structures and Algorithms · doi:10.1002/(sici)1098-2418(199909)15:2<113::aid-rsa1>3.0.co;2-s · Cited by 435
Mézard, M., & Parisi, G. (1985) · Journal de Physique Lettres · doi:10.1051/jphyslet:019850046017077100 · Cited by 220
On the value of a random minimum spanning tree problem
Frieze, A. M. (1985) · Discrete Applied Mathematics · doi:10.1016/0166-218x(85)90058-7 · Cited by 215
A Patching Algorithm for the Nonsymmetric Traveling-Salesman Problem
Karp, R. M. (1979) · SIAM Journal on Computing · doi:10.1137/0208045 · Cited by 177
Asymptotics in the random assignment problem
Aldous, D. (1992) · Probability Theory and Related Fields · doi:10.1007/bf01192719 · Cited by 162
Self-citationOn the Expected Value of a Random Assignment Problem
Walkup, D. W. (1979) · SIAM Journal on Computing · doi:10.1137/0208036 · Cited by 147
Cited by
Information, Physics, and Computation
Mézard, M., & Montanari, A. (2009) · doi:10.1093/acprof:oso/9780198570837.001.0001 · Cited by 1,913
Frieze, A., & Karoński, M. (2015) · doi:10.1017/cbo9781316339831 · Cited by 576
Metadata
- Authors
- Aldous, D. J.
- Venue
- Random Structures & Algorithms
- Publisher
- Wiley
- Published
- 2001-06-20
- Volume
- 18
- Issue
- 4
- Pages
- 381-418
- ISSN
- 1042-9832 (ISSN-L)
- 1098-2418
- OpenAlex
- W1504317671
- Cited by
- 278
- References
- 15
- FWCI
- 34.41
- Type
- journal article
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: The ζ(2) limit in the random assignment problem. https://app.cochat.ai/papers/10.1002/rsa.1015
- The paper
- Aldous, D. J. (2001). The ζ(2) limit in the random assignment problem. Random Structures & Algorithms. https://doi.org/10.1002/rsa.1015
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.
