Approximation and Online Algorithms

DOI10.1007/11671411zbMath1125.68425OpenAlexW4210634114MaRDI QIDQ5898459

David F. Manlove, David J. Abraham, Péter Biró

Publication date: 12 February 2007

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/11671411

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Approximation algorithms (68W25) Matching models (91B68)

Related Items (35)

A new solution concept for the roommate problem: \(\mathcal{Q}\)-stable matchings ⋮ Constrained stable marriage with free edges or few blocking pairs ⋮ Stable matchings of teachers to schools ⋮ Stability against robust deviations in the roommate problem ⋮ Review of the theory of stable matchings and contract systems ⋮ Stochastic stability for roommate markets ⋮ Consistent enlargements of the core in roommate problems ⋮ Computing relaxations for the three-dimensional stable matching problem with cyclic preferences ⋮ Balancing stability and efficiency in team formation as a generalized roommate problem ⋮ Robust and approximately stable marriages under partial information ⋮ Weak stability against robust deviations and the bargaining set in the roommate problem ⋮ ``Almost-stable matchings in the hospitals/residents problem with couples ⋮ ``Almost stable matchings in the roommates problem with bounded preference lists ⋮ Solving hard stable matching problems involving groups of similar agents ⋮ Absorbing sets in roommate problems ⋮ Almost stable matchings by truncating the Gale-Shapley algorithm ⋮ Solutions for the stable roommates problem with payments ⋮ A General Framework for Stable Roommates Problems using Answer Set Programming ⋮ Computing solutions for matching games ⋮ The stable roommates problem with short lists ⋮ How hard is it to satisfy (almost) all roommates ⋮ The stable marriage problem: an interdisciplinary review from the physicist's perspective ⋮ Stable marriage and roommates problems with restricted edges: complexity and approximability ⋮ Stable secretaries ⋮ On random stable partitions ⋮ Size versus stability in the marriage problem ⋮ Instability of matchings in decentralized markets with various preference structures ⋮ The dynamics of stable matchings and half-matchings for the stable marriage and roommates problems ⋮ Impossibilities for roommate problems ⋮ Size Versus Stability in the Marriage Problem ⋮ An improved approximation lower bound for finding almost stable maximum matchings ⋮ A bargaining set for roommate problems ⋮ Balanced stable marriage: how close is close enough? ⋮ The Stable Roommates Problem with Short Lists ⋮ The hospitals/residents problem with lower quotas

This page was built for publication: Approximation and Online Algorithms