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)pprox 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/6pprox 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.
展开▼
机译：在一个具有独立的指数分布边缘成本的$ n $ by $ n $完整二分图中，我们要求一组最小边的总成本，每个顶点至少与每个边相关。这个所谓的最小边缘覆盖问题是对完美匹配的放松。我们证明最小边缘覆盖的大$ n $限制成本为$ W（1）^ 2 + 2W（1）约1.456 $，其中$ W $是Lambert $ W $函数。特别地，这意味着最小边缘覆盖比最小完美匹配便宜，最小完美匹配的极限成本为$ pi ^ 2/6 大约1.645 $。我们通过将完全匹配问题推广到在图的两个顶点集上施加（多）拟阵结构，并要求连接独立集合的规定大小的边集，来获得此结果。
展开▼
