@article{EJP846,
author = {Martin Hessler and Johan Wästlund},
title = {Edge cover and polymatroid flow problems},
journal = {Electron. J. Probab.},
fjournal = {Electronic Journal of Probability},
volume = {15},
year = {2010},
keywords = {Random graphs; Combinatorial optimization},
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.},
pages = {no. 72, 2200-2219},
issn = {1083-6489},
doi = {10.1214/EJP.v15-846},
url = {http://ejp.ejpecp.org/article/view/846}}