Home | Contents | Submissions, editors, etc. | Login | Search | EJP
 Electronic Communications in Probability > Vol. 14 (2009) > Paper 26 open journal systems 


An easy proof of the ζ(2) limit in the random assignment problem

Johan Wästlund, Chalmers University of Technology


Abstract
The edges of the complete bipartite graph $K_{n,n}$ are given independent exponentially distributed costs. Let $C_n$ be the minimum total cost of a perfect matching. It was conjectured by M. MÈzard and G. Parisi in 1985, and proved by D. Aldous in 2000, that $C_n$ converges in probability to $pi^2/6$. We give a short proof of this fact, consisting of a proof of the exact formula $1 + 1/4 + 1/9 + dots + 1/n^2$ for the expectation of $C_n$, and a $O(1/n)$ bound on the variance.


Full text: PDF

Pages: 261-269

Published on: July 5, 2009
Bibliography
  1. D. Aldous. Asymptotics in the random assignment problem, Probab. Theory Relat. Fields 93 (1992) 507-534. Math. Review 94b:60013
  2. D. Aldous. The zeta(2) limit in the random assignment problem, Random Structures Algorithms 18 (2001), no 4. 381-418. Math. Review 2002f:60015
  3. S. E. Alm, and G. B. Sorkin. Exact expectations and distributions in the random assignment problem, Combin. Probab. Comput. 11 (2002), no. 3, 217-248. Math. Review 2003e:60015
  4. R. Brunetti, W. Krauth, M. MŽzard and G. Parisi. Extensive Numerical Simulation of Weighted Matchings: Total Length and Distribuion of Links in the Optimal Solution, Europhys. Lett. 14 4 (1991), 295-301. Math. Review number not available.
  5. M. Buck, C. Chan, and D. Robbins. On the expected value of the minimum assignment, Random Structures & Algorithms 21 (2002), no. 1, 33-58. Math. Review 2003h:15034
  6. D. Coppersmith and G. Sorkin. Constructive Bounds and Exact Expectations For the Random Assignment Problem, Random Structures & Algorithms 15 (1999), 133-144. Math. Review 2001j:05096
  7. D. Coppersmith and G. Sorkin. On the expected incremental cost of a minimum assignment. In Contemporary Mathematics (B. Bollob'as, ed.), Vol. 10 of Bolyai Society Mathematical Studies, Springer. Math. Review number not available.
  8. W. E. Donath. Algorithm and average-value bounds for assignment problems, IBM J. Res. Dev. 13 (1969), 380-386. Math. Review number not available.
  9. V. Dotsenko. Exact solution of the random bipartite matching model, J. Phys. A 33 (2000), 2015-2030. Math. Review number not available.
  10. M. X. Goemans and M. S. Kodialam. A lower bound on the expected cost of an optimal assignment, Math. Oper. Res. 18 (1993), 267-274. Math. Review
  11. T. E. Harris. Lower bound for the critical probability in a certain percolation process, Proc. Cambridge Phil. Soc. 56 (1960), 13-20. Math. Review 94m:90044
  12. J. Houdayer, J. H. Bouter de Monvel and O. C. Martin. Comparing mean field and Euclidean matching problems, Eur. Phys. J. B. 6 (1998), 383-393. Math. Review number not available.
  13. R. Karp. An upper bound on the expected cost of an optimal assignment, In Discrete Algorithms and Complexity: Proceedings of the Japan-U.S. Joint Seminar, Academic Press, 1987, 1-4. Math. Review 88k:90128
  14. R. Karp, A. H. G. Rinnooy Kan and R. V. Vohra. Average case analysis of a heuristic for the assignment problem, Math. Oper. Res. 19 (1994), 513-522. Math. Review 95e:90116
  15. A. J. Lazarus. The assignment problem with uniform (0,1) cost matrix, Master's thesis, Department of Mathematics, Princeton University, Princeton NJ, 1979. Math. Review number not available.
  16. A. J. Lazarus. Certain expected values in the random assignment problem, Oper. Res. Lett. 14 (1993), 207-214. Math. Review 94g:90081
  17. S. Linusson and J. WŠstlund. A generalization of the random assignment problem, arXiv:math.CO/0006146. Math. Review number not available.
  18. S. Linusson and J. WŠstlund. A proof of Parisi's conjecture on the random assignment problem, Probab. Theory Relat. Fields 128 (2004), 419-440. Math. Review 2004m:90102
  19. M. MŽzard and G. Parisi. Replicas and optimization, J. Phys. Lett. 46 (1985), 771-778. Math. Review number not available.
  20. M. MŽzard and G. Parisi. Mean-field equations for the matching and the travelling salesman problems, Europhys. Lett. 2 (1986) 913-918. Math. Review number not available.
  21. M. MŽzard and G. Parisi. On the solution of the random link matching problems, J. Physique Lettres 48 (1987), 1451-1459. Math. Review number not available.
  22. C. Nair, B. Prabhakar and M. Sharma. Proofs of the Parisi and Coppersmith-Sorkin random assignment conjectures, Random Structures and Algorithms 27 No. 4 (2006), 413-444. Math. Review 2006e:90050
  23. B. Olin. Asymptotic properties of the random assignment problem, Ph.D. thesis, Kungl Tekniska Hšgskolan, Stockholm, Sweden, (1992). Math. Review number not available.
  24. P. M. Pardalos and K. G. Ramakrishnan. On the expected optimal value of random assignment problems: Experimental results and open questions, Comput. Optim. Appl. 2 (1993), 261-271. Math. Review number not available.
  25. G. Parisi. A conjecture on random bipartite matching, arXiv:cond-mat/9801176, 1998. Math. Review number not available.
  26. M. Talagrand. Concentration of measure and isoperimetric inequalities in product spaces, Inst. Hautes 'Etudes Sci. Publ. Math. 81 (1995), 73-205. Math. Review 97h:60016
  27. D. W. Walkup. On the expected value of a random assignment problem, SIAM J. Comput. 8 (1979), 440-442. Math. Review 80e:68176
  28. J. WŠstlund. The variance and higher moments in the random assignment problem, Linkšping Studies in Mathematics no 8 (2005). Math. Review number not available.
















Research
Support Tool
Capture Cite
View Metadata
Printer Friendly
Context
Author Address
Action
Email Author
Email Others


Home | Contents | Submissions, editors, etc. | Login | Search | EJP

Electronic Communications in Probability. ISSN: 1083-589X