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

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Edge cover and polymatroid flow problems
Linköping University, Department of Mathematics, Applied Mathematics. Linköping University, The Institute of Technology.
Chalmers.
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
Mathematics
Identifiers
URN: urn:nbn:se:liu:diva-65720ISI: 000285654300001OAI: oai:DiVA.org:liu-65720DiVA: diva2:398512
Available from: 2011-02-18 Created: 2011-02-18 Last updated: 2011-02-18

Open Access in DiVA

No full text

Authority records BETA

Hessler, Martin

Search in DiVA

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

Search outside of DiVA

GoogleGoogle Scholar

urn-nbn

Altmetric score

urn-nbn
Total: 89 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf