A polynomial-time algorithm for the bistable roommates problem

DOI10.1006/JCSS.2001.1791MaRDI QIDQ1604203zbMATH OpenOpenAlexFDO

Authors Jay Sethuraman, Chung-Piaw Teo

Publication date 4 July 2002

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://semanticscholar.org/paper/2d9a6e446bd19e906fefe31298f4bbb6f25a764f, http://scholarbank.nus.edu.sg/handle/10635/44920

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Nonnumerical algorithms (68W05) Analysis of algorithms (68W40) Combinatorial optimization (90C27) Matching models (91B68)

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.

Recommendations

• Bistable versions of the marriages and roommates problems
• An efficient algorithm for the “stable roommates” problem
• The stable fixtures problem -- a many-to-many extension of stable roommates
• The Structure of the Stable Roommate Problem: Efficient Representation and Enumeration of All Stable Assignments
• A maximum stable matching for the roommates problem

Cites work

• An efficient algorithm for the “stable roommates” problem
• Bistable versions of the marriages and roommates problems
• Characterization of stable matchings as extreme points of a polytope
• College Admissions and the Stability of Marriage
• Geometric algorithms and combinatorial optimization
• scientific article; zbMATH DE number 45086 (Why is no real title available?)
• scientific article; zbMATH DE number 48303 (Why is no real title available?)
• scientific article; zbMATH DE number 3558960 (Why is no real title available?)
• Linear programming brings marital bliss
• On a cutting plane heuristic for the stable roommates problem and its applications
• Stable Matchings, Optimal Assignments, and Linear Programming
• The geometry of fractional stable matchings and its applications

Cited in

(6)

• Bistable versions of the marriages and roommates problems
• Jointly stable matchings
• Jointly stable matchings
• Smith and Rawls share a room: stability and medians
• Consistent enlargements of the core in roommate problems
• Impossibilities for roommate problems

This page was built for publication: A polynomial-time algorithm for the bistable roommates problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1604203)