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

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