Please use this identifier to cite or link to this item: https://doi.org/10.1006/jcss.2001.1791
Title: A polynomial-time algorithm for the bistable roommates problem
Authors: Sethuraman, J.
Teo, C.-P. 
Keywords: Bistability
Linear programming
Rounding
Stable matching
Issue Date: 2001
Citation: Sethuraman, J., Teo, C.-P. (2001). A polynomial-time algorithm for the bistable roommates problem. Journal of Computer and System Sciences 63 (3) : 486-497. ScholarBank@NUS Repository. https://doi.org/10.1006/jcss.2001.1791
Abstract: In a recent paper, Weems introduced the bistable matching problem, and asked if a polynomial-time algorithm exists to decide the feasibility of the bistable roommates problem. We resolve this question in the affirmative using linear programming. In addition, we show that several (old and new) results for the bistable marriage and roommates problem become transparent using the polyhedral approach. This technique has been used recently by the authors to address classical stable matching problems.
Source Title: Journal of Computer and System Sciences
URI: http://scholarbank.nus.edu.sg/handle/10635/44920
ISSN: 00220000
DOI: 10.1006/jcss.2001.1791
Appears in Collections:Staff Publications

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

SCOPUSTM   
Citations

6
checked on Oct 12, 2018

WEB OF SCIENCETM
Citations

5
checked on Oct 3, 2018

Page view(s)

76
checked on May 19, 2018

Google ScholarTM

Check

Altmetric


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