陈旭瑾等人发表题为“The Maximum-weight Stable Matching Problem: Duality and Efficiency”论文

2012-08-23 | 撰稿: | 浏览:

论文题目: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.

点击下载论文

科研进展中国科学院数学与系统科学研究院应用数学研究所
地址 北京市海淀区中关村东路55号 思源楼6-7层 南楼5-6、8层 邮编:100190 电子邮箱:iam@amss.ac.cn
@2000-2022 京ICP备05058656号-1