Please use this identifier to cite or link to this item:
|Title:||The geometry of fractional stable matchings and its applications||Authors:||Teo, C.-P.
|Issue Date:||1998||Citation:||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.
checked on Oct 14, 2019
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.