Please use this identifier to cite or link to this item: http://scholarbank.nus.edu.sg/handle/10635/45043
Title: LP based approach to optimal stable matchings
Authors: Teo, Chung-Piaw 
Sethuraman, Jay
Issue Date: 1997
Source: Teo, Chung-Piaw,Sethuraman, Jay (1997). LP based approach to optimal stable matchings. Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms : 710-719. ScholarBank@NUS Repository.
Abstract: 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. This formulation is non-empty if and only if the underlying roommates problem has a stable matching. Furthermore, for certain special weight functions on the edges, we construct a 2-approximation algorithm for the optimal stable roommates problem. Our technique uses a crucial geometry of the fractional solutions in 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 convex combination of stable marriage solutions. This leads to a genuinely simple proof of the integrality of the stable marriage polytope. Based on these ideas, we devise a heuristic to solve the optimal stable roommates problem. The heuristic combines the power of rounding and cutting-plane methods. We present some computational results based on preliminary implementations of this heuristic.
Source Title: Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
URI: http://scholarbank.nus.edu.sg/handle/10635/45043
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

Page view(s)

92
checked on Dec 16, 2017

Google ScholarTM

Check


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.