A polynomial-time algorithm for the bistable roommates problem (Q1604203): Difference between revisions

From MaRDI portal
Import240304020342 (talk | contribs)
Set profile property.
Normalize DOI.
 
(2 intermediate revisions by 2 users not shown)
Property / DOI
 
Property / DOI: 10.1006/jcss.2001.1791 / rank
Normal rank
 
Property / OpenAlex ID
 
Property / OpenAlex ID: W2138100238 / rank
 
Normal rank
Property / cites work
 
Property / cites work: College Admissions and the Stability of Marriage / rank
 
Normal rank
Property / cites work
 
Property / cites work: Geometric algorithms and combinatorial optimization / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3995616 / rank
 
Normal rank
Property / cites work
 
Property / cites work: An efficient algorithm for the “stable roommates” problem / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4130997 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Stable Matchings, Optimal Assignments, and Linear Programming / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3999327 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Characterization of stable matchings as extreme points of a polytope / rank
 
Normal rank
Property / cites work
 
Property / cites work: The Geometry of Fractional Stable Matchings and Its Applications / rank
 
Normal rank
Property / cites work
 
Property / cites work: On a cutting plane heuristic for the stable roommates problem and its applications / rank
 
Normal rank
Property / cites work
 
Property / cites work: Linear programming brings marital bliss / rank
 
Normal rank
Property / cites work
 
Property / cites work: Bistable versions of the marriages and roommates problems / rank
 
Normal rank
Property / DOI
 
Property / DOI: 10.1006/JCSS.2001.1791 / rank
 
Normal rank

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
    0 references
    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

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references