Better and Simpler Approximation Algorithms for the Stable Marriage Problem

DOI10.1007/978-3-540-87744-8_52zbMath1158.90397OpenAlexW2126904726MaRDI QIDQ3541122

Zoltán Király

Publication date: 25 November 2008

Published in: Algorithms - ESA 2008 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-87744-8_52

zbMATH Keywords

approximation algorithmsstable matchinghospitals/residents problem

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Approximation algorithms (68W25) Matching models (91B68)

Related Items (3)

Parameterized complexity and local search approaches for the stable marriage problem with ties ⋮ Linear time local approximation algorithm for maximum stable marriage ⋮ Better and simpler approximation algorithms for the stable marriage problem

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
• Improved approximation results for the stable marriage problem
• College Admissions and the Stability of Marriage

This page was built for publication: Better and Simpler Approximation Algorithms for the Stable Marriage Problem