``Almost stable matchings in the roommates problem with bounded preference lists
DOI10.1016/J.TCS.2012.01.022zbMATH Open1242.68111OpenAlexW2040118257MaRDI QIDQ428844FDOQ428844
Authors: Péter Biró, David F. Manlove, Eric J. McDermid 
Publication date: 25 June 2012
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2012.01.022
Recommendations
Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Cites Work
- On-line algorithms for weighted bipartite matching and stable marriages
- The Hospitals/Residents Problem with Quota Lower Bounds
- Title not available (Why is that?)
- Title not available (Why is that?)
- Approximation and Online Algorithms
- College Admissions and the Stability of Marriage
- Size versus stability in the marriage problem
- An improved approximation lower bound for finding almost stable maximum matchings
- A necessary and sufficient condition for the existence of a complete stable matching
- An efficient algorithm for the “stable roommates” problem
- Pairwise kidney exchange
- Almost stable matchings by truncating the Gale-Shapley algorithm
- Instability of matchings in decentralized markets with various preference structures
- Stable matchings and stable partitions∗
- An upper bound for the solvability probability of a random stable roommates instance
Cited In (18)
- A maximum stable matching for the roommates problem
- The ``stable roommates problem with random preferences
- Strongly stable and maximum weakly stable noncrossing matchings
- Fair assignment of indivisible objects under ordinal preferences
- The stable roommates problem with short lists
- An improved approximation lower bound for finding almost stable maximum matchings
- Stable matchings with covering constraints: a complete computational trichotomy
- A General Framework for Stable Roommates Problems using Answer Set Programming
- Constrained stable marriage with free edges or few blocking pairs
- Computing relaxations for the three-dimensional stable matching problem with cyclic preferences
- The Stable Roommates Problem with Short Lists
- Approximation and Online Algorithms
- How hard is it to satisfy (almost) all roommates
- Balanced stable marriage: how close is close enough?
- On a Random Instance of a ‘Stable Roommates’ Problem: Likely Behavior of the Proposal Algorithm
- Stable Marriage and Roommates Problems with Restricted Edges: Complexity and Approximability
- Stable marriage and roommates problems with restricted edges: complexity and approximability
- ``Almost-stable matchings in the hospitals/residents problem with couples
This page was built for publication: ``Almost stable matchings in the roommates problem with bounded preference lists
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q428844)
