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 (17)

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

This page was built for publication: Better and simpler approximation algorithms for the stable marriage problem