论文题目：The Maximum-weight Stable Matching Problem: Duality and Efficiency
论文作者：Xujin Chen, Guoli Ding, Xiaodong Hu, Wenan Zang
论文摘要: Given a preference system $(G,\prec)$ and an integral weight function defined on the edge set of $G$ (not necessarily bipartite), the maximum-weight stable matching problem is to find a stable matching of $(G,\prec)$ with maximum total weight. In this paper we study this NP-hard problem using linear programming and polyhedral approaches. We show that the Rothblum system for defining the fractional stable matching polytope of $(G,\prec)$ is totally dual integral if and only if this polytope is integral if and only if $(G,\prec)$ has a bipartite representation. We also present a combinatorial polynomial-time algorithm for the maximum-weight stable matching problem and its dual on any preference system with a bipartite representation. Our results generalize Kir′aly and Pap’s theorem on the maximum-weight stable-marriage problem and rely heavily on their work.
附件下载：
