
























As a common generalization of previously solved optimization problems concerning bipartite stable matchings, we describe a strongly polynomial network flow based algorithm for computing $\ell$ disjoint stable matchings with minimum total cost. The major observation behind the approach is that stable matchings, as edge sets, can be represented as certain cuts of an associated directed graph. This allows us to use results on disjoint cuts directly to answer questions about disjoint stable matchings. We also provide a construction that represents stable matchings as maximum-size antichains in a partially ordered set (poset), which enables us to apply the theorems of Dilworth, Mirsky, Greene and Kleitman directly to stable matchings. Another consequence of these approaches is a min-max formula for the minimum number of stable matchings covering all stable edges.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。