Please use this identifier to cite or link to this item: https://scholarbank.nus.edu.sg/handle/10635/44889
DC FieldValue
dc.titleThe geometry of fractional stable matchings and its applications
dc.contributor.authorTeo, C.-P.
dc.contributor.authorSethuraman, J.
dc.date.accessioned2013-10-10T04:36:55Z
dc.date.available2013-10-10T04:36:55Z
dc.date.issued1998
dc.identifier.citationTeo, 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.
dc.identifier.issn0364765X
dc.identifier.urihttp://scholarbank.nus.edu.sg/handle/10635/44889
dc.description.abstractWe 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.
dc.sourceScopus
dc.subjectApproximation algorithms
dc.subjectLinear programming
dc.subjectRounding
dc.subjectStable matching
dc.typeArticle
dc.contributor.departmentDECISION SCIENCES
dc.description.sourcetitleMathematics of Operations Research
dc.description.volume23
dc.description.issue4
dc.description.page874-891
dc.description.codenMORED
dc.identifier.isiutNOT_IN_WOS
Appears in Collections:Staff Publications

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

Page view(s)

78
checked on Oct 14, 2019

Google ScholarTM

Check


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