Approximation and Online Algorithms

DOI10.1007/11671411zbMath1125.68425MaRDI 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

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

68W25: Approximation algorithms

91B68: Matching models

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?, Review of the theory of stable matchings and contract systems, Computing relaxations for the three-dimensional stable matching problem with cyclic preferences, Balancing stability and efficiency in team formation as a generalized roommate problem, Weak stability against robust deviations and the bargaining set in the roommate problem, The hospitals/residents problem with lower quotas, Stable matchings of teachers to schools, ``Almost stable matchings in the roommates problem with bounded preference lists, Stochastic stability for roommate markets, Computing solutions for matching games, Consistent enlargements of the core in roommate problems, Size versus stability in the marriage problem, Impossibilities for roommate problems, An improved approximation lower bound for finding almost stable maximum matchings, ``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, Almost stable matchings by truncating the Gale-Shapley algorithm, Stable secretaries, On random stable partitions, A bargaining set for roommate problems, Constrained stable marriage with free edges or few blocking pairs, Robust and approximately stable marriages under partial information, Solving hard stable matching problems involving groups of similar agents, The stable marriage problem: an interdisciplinary review from the physicist's perspective, Absorbing sets in roommate problems, Solutions for the stable roommates problem with payments, 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, A new solution concept for the roommate problem: \(\mathcal{Q}\)-stable matchings, Stability against robust deviations in the roommate problem, The Stable Roommates Problem with Short Lists, Size Versus Stability in the Marriage Problem