Please use this identifier to cite or link to this item: http://scholarbank.nus.edu.sg/handle/10635/44889
Title: The geometry of fractional stable matchings and its applications
Authors: Teo, C.-P. 
Sethuraman, J.
Keywords: Approximation algorithms
Linear programming
Rounding
Stable matching
Issue Date: 1998
Source: Teo, C.-P.,Sethuraman, J. (1998). The geometry of fractional stable matchings and its applications. Mathematics of Operations Research 23 (4) : 874-891. 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, 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 2-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.
Source Title: Mathematics of Operations Research
URI: http://scholarbank.nus.edu.sg/handle/10635/44889
ISSN: 0364765X
Appears in Collections:Staff Publications

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

Page view(s)

48
checked on Dec 8, 2017

Google ScholarTM

Check


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