A polynomial-time algorithm for the bistable roommates problem
type: Item
instance of: scholarly article
title: A polynomial-time algorithm for the bistable roommates problem
zbMATH Open document ID: 1140.90480
author: Jay Sethuraman
author: Chung-Piaw Teo
published in: Journal of Computer and System Sciences
publication date: 2002-07-04T00:00:00Z
review text: In a recent paper, \textit{B. P. Weems} [J. Comput. Syst. Sci. 59, No. 3, 504--520 (1999; Zbl 0946.90073)] 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.
Mathematics Subject Classification ID: 90C27
Mathematics Subject Classification ID: 68W05
Mathematics Subject Classification ID: 05A05
Mathematics Subject Classification ID: 68W40
Mathematics Subject Classification ID: 91B68
zbMATH DE Number: 1763396
MaRDI profile type: Publication
OpenAlex ID: W2138100238
cites work: College Admissions and the Stability of Marriage
cites work: Geometric algorithms and combinatorial optimization
cites work: Q3995616
cites work: An efficient algorithm for the “stable roommates” problem
cites work: Q4130997
cites work: Stable Matchings, Optimal Assignments, and Linear Programming
cites work: Q3999327
cites work: Characterization of stable matchings as extreme points of a polytope
cites work: The geometry of fractional stable matchings and its applications
cites work: On a cutting plane heuristic for the stable roommates problem and its applications
cites work: Linear programming brings marital bliss
cites work: Bistable versions of the marriages and roommates problems
DOI: 10.1006/JCSS.2001.1791
description: scientific article; zbMATH DE number 1763396