The stable roommates problem with short lists

DOI10.1007/s00224-017-9810-9zbMath1418.91387OpenAlexW2758665439WikidataQ59613399 ScholiaQ59613399MaRDI QIDQ1733384

Robert W. Irving, David F. Manlove, Ágnes Cseh

Publication date: 21 March 2019

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00224-017-9810-9

zbMATH Keywords

complexityapproximation algorithmstable matchingbounded length preference lists

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Matching models (91B68)

Related Items (3)

Computing relaxations for the three-dimensional stable matching problem with cyclic preferences ⋮ A General Framework for Stable Roommates Problems using Answer Set Programming ⋮ Parameterized complexity of stable roommates with ties and incomplete lists through the lens of graph parameters

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• ``Almost stable matchings in the roommates problem with bounded preference lists
• Size versus stability in the marriage problem
• An improved approximation lower bound for finding almost stable maximum matchings
• A bounded approximation for the minimum cost 2-sat problem
• A new fixed point approach for stable networks and stable marriages
• Some simplified NP-complete graph problems
• Network flow and 2-satisfiability
• Hard variants of stable marriage.
• Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
• The Geometry of Fractional Stable Matchings and Its Applications
• The Stable Roommates Problem with Ties
• A necessary and sufficient condition for the existence of a complete stable matching
• NP-complete stable matching problems
• An efficient algorithm for the “stable roommates” problem
• Three Fast Algorithms for Four Problems in Stable Marriage
• How hard is it to satisfy (almost) all roommates
• Algorithmics of Matching Under Preferences
• Approximation and Online Algorithms
• College Admissions and the Stability of Marriage

This page was built for publication: The stable roommates problem with short lists