Home | Contents | Submissions, editors, etc. | Login | Search | EJP
 Electronic Communications in Probability > Vol. 13 (2008) > Paper 25 open journal systems 


Random matching problems on the complete graph

Johan Wästlund, Department of Mathematical Sciences, Chalmers University of Technology, Göteborg, Sweden


Abstract
The edges of the complete graph on n vertices are assigned independent exponentially distributed costs. A k-matching is a set of k edges of which no two have a vertex in common. We obtain explicit bounds on the expected value of the minimum total cost C_{k,n} of a k-matching. In particular we prove that if n = 2k then π2/12 < EC_{k,n} < π2/12 + log n/n.


Full text: PDF

Pages: 258-265

Published on: May 12, 2008
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), 381-418. Math. Review 2002f:60015
  3. D. Coppersmith and G. Sorkin. Constructive bounds and exact expectations for the random assignment problem. Random Structures Algorithms 15 (1999), 113-144. Math. Review 2001j:05096
  4. 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
  5. M. Mézard and G. Parisi. Replicas and optimization. Journal de Physique Lettres 46 (1985), 771-778. Math. Review number not available.
  6. M. Mézard and G. Parisi. On the solution of the random link matching problems. Journal de Physique Lettres 48 (1987), 1451-1459. Math. Review number not available.
  7. C. Nair, B. Prabhakar and M. Sharma. Proofs of the Parisi and Coppersmith-Sorkin random assignment conjectures. Random Structures Algorithms 27 (2005), 413-444. Math. Review 2006e:90050
  8. G. Parisi, Giorgio. A conjecture on random bipartite matching. arXiv:cond-mat/9801176 (1998). Math. Review number not available.
  9. J. Wästlund, Johan. An easy proof of the zeta(2) limit in the random assignment problem. 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