The Stable Roommates Problem with Short Lists

DOI10.1007/978-3-662-53354-3_17zbMath1403.91255arXiv1605.04609OpenAlexW2406669955MaRDI QIDQ2819460

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

Publication date: 29 September 2016

Published in: Algorithmic Game Theory (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1605.04609

zbMATH Keywords

stable roommates problemincomplete preference lists, egalitarian stable matching

Mathematics Subject Classification ID

Matching models (91B68)

Related Items (2)

How hard is it to satisfy (almost) all roommates ⋮ The Stable Roommates Problem with Short Lists

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
• 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 Short Lists
• 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
• 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