A 25/17-approximation algorithm for the stable marriage problem with one-sided ties

DOI10.1007/978-3-642-15781-3_12MaRDI QIDQ3586389zbMATH OpenOpenAlexFDO

Authors Shuichi Miyazaki, Hiroki Yanagisawa, 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

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Matching models (91B68)

Recommendations

• A 25/17-approximation algorithm for the stable marriage problem with one-sided ties
• A 1.875-approximation algorithm for the stable marriage problem
• An improved approximation algorithm for the stable marriage problem with one-sided ties
• Algorithms and Computation
• A \((2-c\frac{1}{\sqrt{N}})\)-approximation algorithm for the stable marriage problem

Cited in

(12)

• 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
• Improved approximation bounds for the student-project allocation problem with preferences over projects
• Stable marriage with general preferences
• A \((1 + 1/e)\)-approximation algorithm for maximum stable matching with one-sided ties and incomplete lists
• A 25/17-approximation algorithm for the stable marriage problem with one-sided ties
• A tight approximation bound for the stable marriage problem with restricted ties
• An improved approximation algorithm for the stable marriage problem with one-sided ties
• Maximum stable matching with one-sided ties of bounded length
• Maximum stable matching with one-sided ties of bounded length

This page was built for publication: A 25/17-approximation algorithm for the stable marriage problem with one-sided ties

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3586389)