CPL - Chalmers Publication Library
| Utbildning | Forskning | Styrkeområden | Om Chalmers | In English In English Ej inloggad.

Edge cover and polymatroid flow problems

Martin Hessler ; Johan Wästlund (Institutionen för matematiska vetenskaper, matematik)
Electronic Journal of Probability (1083-6489). Vol. 15 (2010), p. 2200-2219.
[Artikel, refereegranskad vetenskaplig]

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.

Nyckelord: Random graphs, Combinatorial optimization



Denna post skapades 2011-03-01. Senast ändrad 2011-04-01.
CPL Pubid: 137437

 

Läs direkt!

Lokal fulltext (fritt tillgänglig)


Institutioner (Chalmers)

Institutionen för matematiska vetenskaper, matematik (2005-2016)

Ämnesområden

Matematisk statistik

Chalmers infrastruktur