Improved approximation results for the stable marriage problem

DOI10.1145/1273340.1273346zbMath1192.68903OpenAlexW2071503214MaRDI QIDQ3580942

Magnús M. Halldórsson, Hiroki Yanagisawa, Miyazaki Shuichi, Kazuo Iwama

Publication date: 14 August 2010

Published in: ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1273340.1273346

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Combinatorics in computer science (68R05) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Approximation algorithms (68W25) Matching models (91B68)

Related Items (21)

Review of the theory of stable matchings and contract systems ⋮ Improved approximation algorithms for two variants of the stable marriage problem with ties ⋮ Cutoff stability under distributional constraints with an application to summer internship matching ⋮ On the approximability of the stable matching problem with ties of size two ⋮ Improved approximation bounds for the student-project allocation problem with preferences over projects ⋮ Better and Simpler Approximation Algorithms for the Stable Marriage Problem ⋮ Maximum locally stable matchings ⋮ Linear time local approximation algorithm for maximum stable marriage ⋮ Local search approaches in stable matching problems ⋮ Faster and simpler approximation of stable matchings ⋮ Mathematical models for stable matching problems with ties and incomplete lists ⋮ Improved Approximation Bounds for the Student-Project Allocation Problem with Preferences over Projects ⋮ Stable marriage with general preferences ⋮ A 25/17-approximation algorithm for the stable marriage problem with one-sided ties ⋮ Better and simpler approximation algorithms for the stable marriage problem ⋮ Maximum stable matching with one-sided ties of bounded length ⋮ Envy-freeness and relaxed stability: hardness and approximation algorithms ⋮ Stable Matching with Uncertain Linear Preferences ⋮ Stable matching with uncertain linear preferences ⋮ Approximability of Economic Equilibrium for Housing Markets with Duplicate Houses ⋮ The hospitals/residents problem with lower quotas

This page was built for publication: Improved approximation results for the stable marriage problem