``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-hardnessblocking pairspolynomial-time algorithmstable roommates problem

Mathematics Subject Classification ID

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

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

• 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
• scientific article; zbMATH DE number 45086 (Why is no real title available?)
• scientific article; zbMATH DE number 3558960 (Why is no real title available?)
• 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

(21)

• ``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
• Multidimensional stable roommates with master list
• The Stable Roommates Problem with Short Lists
• Stable marriage and roommates problems with restricted edges: complexity and approximability
• On a Random Instance of a ‘Stable Roommates’ Problem: Likely Behavior of the Proposal Algorithm
• How hard is it to satisfy (almost) all roommates?
• A General Framework for Stable Roommates Problems using Answer Set Programming
• Approximation and Online Algorithms
• Balanced stable marriage: how close is close enough?
• Computing relaxations for the three-dimensional stable matching problem with cyclic preferences
• On the (parameterized) complexity of almost stable marriage
• The ``stable roommates problem with random preferences
• Maximum-utility popular matchings with bounded instability
• Fair assignment of indivisible objects under ordinal preferences
• A maximum stable matching for the roommates problem
• An improved approximation lower bound for finding almost stable maximum matchings

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)