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

approximation algorithmbounded length preference listscomplexitystable matching

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

• ``Almost stable matchings in the roommates problem with bounded preference lists
• 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?
• 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?)
• Network flow and 2-satisfiability
• NP-complete stable matching problems
• Size versus stability in the marriage problem
• Some simplified NP-complete graph problems
• The geometry of fractional stable matchings and its applications
• The Stable Roommates Problem with Ties
• Three Fast Algorithms for Four Problems in Stable Marriage
• Vertex cover might be hard to approximate to within \(2 - \varepsilon \)

Cited in

(16)

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

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)