Better and simpler approximation algorithms for the stable marriage problem

DOI10.1007/s00453-009-9371-7zbMath1216.68341OpenAlexW4253633138MaRDI QIDQ547284

Zoltán Király

Publication date: 1 July 2011

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-009-9371-7

zbMATH Keywords

approximation algorithmsstable matchinghospitals/residents problem

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Matching models (91B68)

Related Items

On Treewidth and Stable Marriage: Parameterized Algorithms and Hardness Results (Complete Characterization), Improved approximation algorithms for two variants of the stable marriage problem with ties, On the number of employed in the matching model, 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, Application of pair approximation method to modeling and analysis of a marriage network, 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, Improved Approximation Bounds for the Student-Project Allocation Problem with Preferences over Projects, A 25/17-approximation algorithm for the stable marriage problem with one-sided ties, Unnamed Item, Maximum stable matching with one-sided ties of bounded length, Student-project allocation with preferences over projects: algorithmic and experimental results, Unnamed Item, Popular Matchings with Lower Quotas

Cites Work

• Unnamed Item
• Unnamed Item
• Approximation algorithms for hard variants of the stable marriage and hospitals/residents problems
• Approximability results for stable marriage problems with ties.
• Hard variants of stable marriage.
• Randomized approximation of the stable marriage problem
• Better and Simpler Approximation Algorithms for the Stable Marriage Problem
• Improved approximation results for the stable marriage problem
• Approximation Algorithms for the Sex-Equal Stable Marriage Problem
• A 3/2-Approximation Algorithm for General Stable Marriage
• Finding large stable matchings
• College Admissions and the Stability of Marriage