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

DOI10.1016/J.TCS.2012.01.022MaRDI QIDQ428844zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

approximation algorithmAPX-hardnesspolynomial-time algorithmstable roommates problemblocking pairs

Mathematics Subject Classification ID

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)

Recommendations

• Approximation and Online Algorithms
• The Stable Roommates Problem with Short Lists
• The stable roommates problem with short lists
• How hard is it to satisfy (almost) all roommates?
• Stable marriage and roommates problems with restricted edges: complexity and approximability

Cites work

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

Cited in

(19)

• Fair assignment of indivisible objects under ordinal preferences
• On a Random Instance of a ‘Stable Roommates’ Problem: Likely Behavior of the Proposal Algorithm
• The stable roommates problem with short lists
• Constrained stable marriage with free edges or few blocking pairs
• An improved approximation lower bound for finding almost stable maximum matchings
• A General Framework for Stable Roommates Problems using Answer Set Programming
• A maximum stable matching for the roommates problem
• The Stable Roommates Problem with Short Lists
• Stable marriage and roommates problems with restricted edges: complexity and approximability
• The ``stable roommates problem with random preferences
• Stable marriage and roommates problems with restricted edges: complexity and approximability
• 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
• ``Almost-stable matchings in the hospitals/residents problem with couples
• Stable matchings with covering constraints: a complete computational trichotomy
• Approximation and Online Algorithms
• Strongly stable and maximum weakly stable noncrossing matchings
• Multidimensional stable roommates with master list

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)