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

DOI10.1016/j.tcs.2012.01.022zbMath1242.68111MaRDI 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 algorithm; polynomial-time algorithm; stable roommates problem; APX-hardness; blocking pairs

Mathematics Subject Classification ID

05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

05C85: Graph algorithms (graph-theoretic aspects)

68W25: Approximation algorithms

Related Items

A General Framework for Stable Roommates Problems using Answer Set Programming, How hard is it to satisfy (almost) all roommates, Balanced stable marriage: how close is close enough?, 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, The stable roommates problem with short lists, Stable marriage and roommates problems with restricted edges: complexity and approximability, Strongly stable and maximum weakly stable noncrossing matchings, Constrained stable marriage with free edges or few blocking pairs, Stable matchings with covering constraints: a complete computational trichotomy, The Stable Roommates Problem with Short Lists, Stable Marriage and Roommates Problems with Restricted Edges: Complexity and Approximability

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