The Stable Roommates Problem with Short Lists
From MaRDI portal
Abstract: We consider two variants of the classical Stable Roommates problem with Incomplete (but strictly ordered) preference lists SRI that are degree constrained, i.e., preference lists are of bounded length. The first variant, EGAL d-SRI, involves finding an egalitarian stable matching in solvable instances of SRI with preference lists of length at most d. We show that this problem is NP-hard even if d=3. On the positive side we give a (2d+3)/7-approximation algorithm for d={3,4,5} which improves on the known bound of 2 for the unbounded preference list case. In the second variant of SRI, called d-SRTI, preference lists can include ties and are of length at most d. We show that the problem of deciding whether an instance of d-SRTI admits a stable matching is NP-complete even if d=3. We also consider the "most stable" version of this problem and prove a strong inapproximability bound for the d=3 case. However for d=2 we show that the latter problem can be solved in polynomial time.
Recommendations
- The stable roommates problem with short lists
- The strongly stable roommates problem
- Stable roommates problem with random preferences
- The Stable Roommates Problem with Choice Functions
- The stable roommates problem with choice functions
- Small random instances of the stable roommates problem
- The ``stable roommates problem with random preferences
- On a generalization of the stable roommates problem
- The roommates problem revisited
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.
- 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
- The geometry of fractional stable matchings and its applications
- The Stable Roommates Problem with Short Lists
- 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
(10)- The stable roommates problem with short lists
- Stable roommate with narcissistic, single-peaked, and single-crossing preferences
- 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 note on roommate problems with a limited number of rooms
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 Q2819460)
