liu.seSearch for publications in DiVA
Change search
ReferencesLink to record
Permanent link

Direct link
Edge cover and polymatroid flow problems
Linköping University, Department of Mathematics, Applied Mathematics. Linköping University, The Institute of Technology.
2010 (English)In: ELECTRONIC JOURNAL OF PROBABILITY, ISSN 1083-6489, Vol. 15, 2200-2219 p.Article in journal (Refereed) Published
Abstract [en]

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) approximate to 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 approximate to 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.

Place, publisher, year, edition, pages
Institute of Mathematical Statistics , 2010. Vol. 15, 2200-2219 p.
Keyword [en]
Random graphs, Combinatorial optimization
National Category
URN: urn:nbn:se:liu:diva-65720ISI: 000285654300001OAI: diva2:398512
Available from: 2011-02-18 Created: 2011-02-18 Last updated: 2011-02-18

Open Access in DiVA

No full text

Search in DiVA

By author/editor
Hessler, Martin
By organisation
Applied MathematicsThe Institute of Technology

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 81 hits
ReferencesLink to record
Permanent link

Direct link