Random matching problems on the complete graph
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 $\pi^2/12 < EC_{k,n} < \pi^2/12 + \log n/n$.
Full Text: Download PDF | View PDF online (requires PDF plugin)
Pages: 258-265
Publication Date: May 12, 2008
DOI: 10.1214/ECP.v13-1372
References
- D. Aldous. Asymptotics in the random assignment problem. Probab. Theory Relat. Fields 93 (1992), 507-534. Math. Review 94b:60013
- D. Aldous. The zeta(2) limit in the random assignment problem. Random Structures Algorithms 18 (2001), 381-418. Math. Review 2002f:60015
- 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
- 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
- M. MÃzard and G. Parisi. Replicas and optimization. Journal de Physique Lettres 46 (1985), 771-778. Math. Review number not available.
- 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.
- 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
- G. Parisi, Giorgio. A conjecture on random bipartite matching. arXiv:cond-mat/9801176 (1998). Math. Review number not available.
- J. Wâ°stlund, Johan. An easy proof of the zeta(2) limit in the random assignment problem. Math. Review number not available.
This work is licensed under a Creative Commons Attribution 3.0 License.