Sökning: onr:"swepub:oai:DiVA.org:liu-65720" >
Edge cover and poly...
Edge cover and polymatroid flow problems
-
- Hessler, Martin (författare)
- Linköpings universitet,Tillämpad matematik,Tekniska högskolan
-
- Wästlund, Johan, 1971 (författare)
- Gothenburg University,Göteborgs universitet,Institutionen för matematiska vetenskaper, matematik,Department of Mathematical Sciences, Mathematics,Chalmers
-
(creator_code:org_t)
- Institute of Mathematical Statistics, 2010
- 2010
- Engelska.
-
Ingår i: Electronic Journal of Probability. - : Institute of Mathematical Statistics. - 1083-6489. ; 15, s. 2200-2219
- Relaterad länk:
-
http://publications.... (primary) (free)
-
visa fler...
-
https://gup.ub.gu.se... (primary) (free)
-
https://urn.kb.se/re...
-
https://research.cha...
-
https://gup.ub.gu.se...
-
visa färre...
Abstract
Ämnesord
Stäng
- 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.
Ämnesord
- NATURVETENSKAP -- Matematik (hsv//swe)
- NATURAL SCIENCES -- Mathematics (hsv//eng)
- NATURVETENSKAP -- Matematik -- Sannolikhetsteori och statistik (hsv//swe)
- NATURAL SCIENCES -- Mathematics -- Probability Theory and Statistics (hsv//eng)
Nyckelord
- Random graphs
- Combinatorial optimization
- MATHEMATICS
- MATEMATIK
- Random graphs
- Combinatorial optimization
Publikations- och innehållstyp
- ref (ämneskategori)
- art (ämneskategori)
Hitta via bibliotek
Till lärosätets databas