A polynomial-time algorithm for the bistable roommates problem (Q1604203): Difference between revisions
From MaRDI portal
Latest revision as of 22:28, 10 December 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A polynomial-time algorithm for the bistable roommates problem |
scientific article |
Statements
A polynomial-time algorithm for the bistable roommates problem (English)
0 references
4 July 2002
0 references
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.
0 references