Random polymatroid flow problems
Martin Hessler, Johan Wästlund · 2010
We generalize the so-called random assignment problem to a setting where we impose a polymatroid structure on the two vertex-sets of a complete bipartite graph, and ask for an edge set of prescribed size connecting independent sets. As an application, we show that under independent exponential edge-costs, the cost of the cheapest edge set covering all vertices of an n by n bipartite graph is asymptotically W (1) 2 +2W (1) ≈ 1.456, where W is the Lambert W-function. In particular it is essentially cheaper than the cheapest perfect matching, whose cost is asymptotically π² /6 ≈ 1.645.