A \((2-c\frac{1}{\sqrt{N}})\)-approximation algorithm for the stable marriage problem

DOI10.1007/S00453-007-9101-YzbMath1141.91301OpenAlexW2030655102MaRDI QIDQ930600

Naoya Yamauchi, Kazuo Iwama, Shuichi Miyazaki

Publication date: 1 July 2008

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-007-9101-y

zbMATH Keywords

Approximation algorithmsTiesIncomplete listsThe stable marriage problem

Mathematics Subject Classification ID

Computational methods for problems pertaining to game theory, economics, and finance (91-08) Matching models (91B68) Software, source code, etc. for problems pertaining to game theory, economics, and finance (91-04)

Related Items (4)

Satisfied two-sided matching: a method considering elation and disappointment of agents ⋮ The aviation technology two-sided matching with the expected time based on the probabilistic linguistic preference relations ⋮ Faster and simpler approximation of stable matchings ⋮ A 25/17-approximation algorithm for the stable marriage problem with one-sided ties

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Ramsey numbers and an approximation algorithm for the vertex cover problem
• Some remarks on the stable matching problem
• Stable marriage and indifference
• Approximability results for stable marriage problems with ties.
• Hard variants of stable marriage.
• Randomized approximation of the stable marriage problem
• STACS 2004
• Algorithm Theory - SWAT 2004
• A Fixed-Point Approach to Stable Matchings and Some Applications
• Algorithms and Computation
• Algorithms - ESA 2003
• College Admissions and the Stability of Marriage
• On the complexity of exchange-stable roommates

This page was built for publication: A \((2-c\frac{1}{\sqrt{N}})\)-approximation algorithm for the stable marriage problem