Sökning: onr:"swepub:oai:DiVA.org:liu-65720" >
Edge cover and poly...
-
Hessler, MartinLinköpings universitet,Tillämpad matematik,Tekniska högskolan
(författare)
Edge cover and polymatroid flow problems
- Artikel/kapitelEngelska2010
Förlag, utgivningsår, omfång ...
-
Institute of Mathematical Statistics,2010
-
printrdacarrier
Nummerbeteckningar
-
LIBRIS-ID:oai:DiVA.org:liu-65720
-
https://urn.kb.se/resolve?urn=urn:nbn:se:liu:diva-65720URI
-
https://research.chalmers.se/publication/137437URI
-
https://gup.ub.gu.se/publication/137437URI
Kompletterande språkuppgifter
-
Språk:engelska
-
Sammanfattning på:engelska
Ingår i deldatabas
Klassifikation
-
Ämneskategori:ref swepub-contenttype
-
Ämneskategori:art swepub-publicationtype
Anmärkningar
-
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 och genrebeteckningar
Biuppslag (personer, institutioner, konferenser, titlar ...)
-
Wästlund, Johan,1971Gothenburg University,Göteborgs universitet,Institutionen för matematiska vetenskaper, matematik,Department of Mathematical Sciences, Mathematics,Chalmers(Swepub:cth)wastlund
(författare)
-
Linköpings universitetTillämpad matematik
(creator_code:org_t)
Sammanhörande titlar
-
Ingår i:Electronic Journal of Probability: Institute of Mathematical Statistics15, s. 2200-22191083-6489
Internetlänk
Hitta via bibliotek
Till lärosätets databas