Please use this identifier to cite or link to this item:
|Title:||LP based approach to optimal stable matchings|
|Authors:||Teo, Chung-Piaw |
|Citation:||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|
|Appears in Collections:||Staff Publications|
Show full item record
Files in This Item:
There are no files associated with this item.
checked on Dec 22, 2018
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.