The stable roommates problem with short lists

DOI10.1007/S00224-017-9810-9MaRDI QIDQ1733384zbMATH OpenOpenAlexWikidataFDO

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

Publication date 21 March 2019

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

Copyright license Creative Commons Attribution 4.0 International

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)

Recommendations

• The Stable Roommates Problem with Short Lists
• ``Almost stable matchings in the roommates problem with bounded preference lists
• Approximation and Online Algorithms
• The Stable Roommates Problem with Ties
• How hard is it to satisfy (almost) all roommates?

Cites work

• scientific article; zbMATH DE number 45086 (Why is no real title available?)
• scientific article; zbMATH DE number 1369412 (Why is no real title available?)
• scientific article; zbMATH DE number 6472649 (Why is no real title available?)
• A bounded approximation for the minimum cost 2-sat problem
• A necessary and sufficient condition for the existence of a complete stable matching
• A new fixed point approach for stable networks and stable marriages
• Algorithmics of matching under preferences. With a foreword by Kurt Mehlhorn
• An efficient algorithm for the “stable roommates” problem
• An improved approximation lower bound for finding almost stable maximum matchings
• Approximation and Online Algorithms
• College Admissions and the Stability of Marriage
• Hard variants of stable marriage.
• How hard is it to satisfy (almost) all roommates?
• NP-complete stable matching problems
• Network flow and 2-satisfiability
• Size versus stability in the marriage problem
• Some simplified NP-complete graph problems
• The Stable Roommates Problem with Ties
• The geometry of fractional stable matchings and its applications
• Three Fast Algorithms for Four Problems in Stable Marriage
• Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
• ``Almost stable matchings in the roommates problem with bounded preference lists

Cited in

(14)

• The three-dimensional stable roommates problem with additively separable preferences
• Egalitarian roommate allocations: complexity and stability
• Two’s Company, Three’s a Crowd: Stable Family and Threesome Roommates Problems
• ``Almost stable matchings in the roommates problem with bounded preference lists
• A General Framework for Stable Roommates Problems using Answer Set Programming
• The Stable Roommates Problem with Short Lists
• The Stable Roommates Problem with Ties
• A note on roommate problems with a limited number of rooms
• How hard is it to satisfy (almost) all roommates?
• Parameterized complexity of stable roommates with ties and incomplete lists through the lens of graph parameters
• Stable roommate with narcissistic, single-peaked, and single-crossing preferences
• Computing relaxations for the three-dimensional stable matching problem with cyclic preferences
• Approximation and Online Algorithms
• Multidimensional stable roommates with master list

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

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