Edge cover and polymatroid flow problems

Martin Hessler (Linköping University)
Johan Wästlund (Chalmers University of Technology)

Abstract


In an $n$ by $n$ complete bipartite graph with independent exponentially distributed edge costs, we ask for the minimum total cost of a set of edges of which each vertex is incident to at least one. This so-called minimum edge cover problem is a relaxation of perfect matching. We show that the large $n$ limit cost of the minimum edge cover is $W(1)^2+2W(1)\approx 1.456$, where $W$ is the Lambert $W$-function. In particular this means that the minimum edge cover is essentially cheaper than the minimum perfect matching, whose limit cost is $\pi^2/6\approx 1.645$. We obtain this result through a generalization of the perfect matching problem to a setting where we impose a (poly-)matroid structure on the two vertex-sets of the graph, and ask for an edge set of prescribed size connecting independent sets.

Full Text: Download PDF | View PDF online (requires PDF plugin)

Pages: 2200-2219

Publication Date: December 18, 2010

DOI: 10.1214/EJP.v15-846

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 and Algorithms 18:4 (2001), 381-418. Math. Review 2002f:60015
  3. M. W. Buck, C. S. Chan and D. P. Robbins. On the Expected Value of the Minimum Assignment. Random Structures and Algorithms 21:1 (2002), 33-58. Math. Review 2003h:15034
  4. J. Edmonds. Submodular functions, matroids and certain polyhedra. Proc. Int. Conf. on Combinatorics, Calgary 1970. Math. Review number not available.
  5. E. Lawler. Combinatorial Optimization: Networks and Matroids. Holt, Rinehart and Winston 1976. Math. Review number not available.
  6. 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
  7. M. Mézard and G. Parisi. Replicas and optimization. Journal de Physique Lettres 46 (1985), 771-778. Math. Review number not available.
  8. C. Nair, B. Prabhakar and M. Sharma. Proofs of the Parisi and Coppersmith-Sorkin random assignment conjectures. Random Structures and Algorithms 27:4 (2005), 413-444. Math. Review 2006e:90050
  9. C. Nair. Proofs of the Parisi and Coppersmith-Sorkin conjectures in the finite random assignment problem. PhD thesis, Stanford University 2005. Math. Review number not available.
  10. G. Parisi. A conjecture on random bipartite matching. arXiv:cond-mat/9801176, 1998. Math. Review number not available.
  11. D. J. A. Welsh. Matroid Theory. Academic Press, London 1976. Math. Review number not available.
  12. J. Wästlund. A Proof of a Conjecture of Buck, Chan and Robbins on the Expected Value of the Minimum Assignment. Random Structures and Algorithms 26:1-2 (2005), 237-251. Math. Review 2005j:60021
  13. J. Wästlund. Random matching problems on the complete graph. Electronic Communications in Probability 13 (2008), 258-265. Math. Review 2009k:60027
  14. J. Wästlund. An easy proof of the zeta(2) limit in the assignment problem. Electronic Communications in Probability 14 (2009), 261-269. Math. Review 2010h:05280
  15. J. Wästlund. The Mean Field Traveling Salesman and Related Problems. Acta Mathematica 204:1 (2010), 91-150. Math. Review number not available.
Bookmark and Share


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