The PDF file you selected should load here if your Web browser has a PDF reader plug-in installed (for example, a recent version of Adobe Acrobat Reader).

Alternatively, you can also download the PDF file directly to your computer, from where it can be opened using a PDF reader. To download the PDF, click the Download link below.

If you would like more information about how to print, save, and work with PDFs, Highwire Press provides a helpful Frequently Asked Questions about PDFs.

Download this PDF file Fullscreen Fullscreen Off

References

  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.
Bookmark and Share


Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.