A 25/17-Approximation Algorithm for the Stable Marriage Problem with One-Sided Ties
From MaRDI portal
Publication:3586389
DOI10.1007/978-3-642-15781-3_12zbMath1287.68181OpenAlexW2135834608MaRDI QIDQ3586389
Hiroki Yanagisawa, Shuichi Miyazaki, Kazuo Iwama
Publication date: 6 September 2010
Published in: Algorithms – ESA 2010 (Search for Journal in Brave)
Full work available at URL: http://hdl.handle.net/2433/226941
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Matching models (91B68)
Related Items (6)
Improved approximation bounds for the student-project allocation problem with preferences over projects ⋮ 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 ⋮ Stable marriage with general preferences
This page was built for publication: A 25/17-Approximation Algorithm for the Stable Marriage Problem with One-Sided Ties
