# zbMATH — the first resource for mathematics

Edge cover and polymatroid flow problems. (English) Zbl 1226.90124
Summary: 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) \approx 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 \approx 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.

##### MSC:
 90C35 Programming involving graphs or networks 90C27 Combinatorial optimization 60C05 Combinatorial probability
Full Text: