``Almost stable matchings in the roommates problem with bounded preference lists

DOI10.1016/j.tcs.2012.01.022zbMath1242.68111OpenAlexW2040118257MaRDI QIDQ428844

David F. Manlove, Péter Biró, 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

zbMATH Keywords

approximation algorithmpolynomial-time algorithmstable roommates problemAPX-hardnessblocking pairs

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (13)

Stable Marriage and Roommates Problems with Restricted Edges: Complexity and Approximability ⋮ Constrained stable marriage with free edges or few blocking pairs ⋮ Computing relaxations for the three-dimensional stable matching problem with cyclic preferences ⋮ Fair assignment of indivisible objects under ordinal preferences ⋮ ``Almost-stable matchings in the hospitals/residents problem with couples ⋮ A General Framework for Stable Roommates Problems using Answer Set Programming ⋮ The stable roommates problem with short lists ⋮ How hard is it to satisfy (almost) all roommates ⋮ Strongly stable and maximum weakly stable noncrossing matchings ⋮ Stable marriage and roommates problems with restricted edges: complexity and approximability ⋮ Balanced stable marriage: how close is close enough? ⋮ The Stable Roommates Problem with Short Lists ⋮ Stable matchings with covering constraints: a complete computational trichotomy

Cites Work

• Unnamed Item
• Unnamed Item
• Pairwise kidney exchange
• Size versus stability in the marriage problem
• An improved approximation lower bound for finding almost stable maximum matchings
• On-line algorithms for weighted bipartite matching and stable marriages
• Almost stable matchings by truncating the Gale-Shapley algorithm
• Instability of matchings in decentralized markets with various preference structures
• The Hospitals/Residents Problem with Quota Lower Bounds
• A necessary and sufficient condition for the existence of a complete stable matching
• An efficient algorithm for the “stable roommates” problem
• Stable matchings and stable partitions^∗
• An upper bound for the solvability probability of a random stable roommates instance
• Approximation and Online Algorithms
• College Admissions and the Stability of Marriage

This page was built for publication: ``Almost stable matchings in the roommates problem with bounded preference lists