The stable roommates problem with short lists
From MaRDI portal
Publication:1733384
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
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
