The geometry of fractional stable matchings and its applications

• 成果类型: Article
• 署名作者: Teo, CP; Sethuraman, J
• 署名单位: National University of Singapore; Massachusetts Institute of Technology (MIT)
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.23.4.874
• 发表日期: 1998
• 页码: 874-891
• 关键词: efficient algorithm

摘要

We study the classical stable marriage and stable roommates problems using a polyhedral approach. We propose a new LP formulation for the stable roommates problem, which has a feasible solution if and only if the underlying roommates problem has a stable matching. Furthermore, for certain special weight functions on the edges, we construct a a-approximation algorithm for the optimal stable roommates problem. Our technique exploits features of the geometry of fractional solutions of this formulation. For the stable marriage problem, we show that a related geometry allows us to express any fractional solution in the stable marriage polytope as a convex combination of stable marriage solutions. This also leads to a genuinely simple proof of the integrality of the stable marriage polytope.