A (2-c1N)-approximation algorithm for the stable marriage problem

DOI10.1007/S00453-007-9101-YMaRDI QIDQ930600zbMATH OpenOpenAlexFDO

Authors Kazuo Iwama, Shuichi Miyazaki, Naoya Yamauchi

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

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

Recommendations

• Algorithms and Computation
• Algorithm Theory - SWAT 2004
• A 1.875-approximation algorithm for the stable marriage problem
• Improved approximation of the stable marriage problem
• Improved approximation results for the stable marriage problem

Cites work

• scientific article; zbMATH DE number 1617265 (Why is no real title available?)
• scientific article; zbMATH DE number 3643026 (Why is no real title available?)
• scientific article; zbMATH DE number 3869066 (Why is no real title available?)
• scientific article; zbMATH DE number 45086 (Why is no real title available?)
• scientific article; zbMATH DE number 1305096 (Why is no real title available?)
• scientific article; zbMATH DE number 1342147 (Why is no real title available?)
• scientific article; zbMATH DE number 1962834 (Why is no real title available?)
• scientific article; zbMATH DE number 2038736 (Why is no real title available?)
• scientific article; zbMATH DE number 1405659 (Why is no real title available?)
• scientific article; zbMATH DE number 1420901 (Why is no real title available?)
• scientific article; zbMATH DE number 1445320 (Why is no real title available?)
• scientific article; zbMATH DE number 6469133 (Why is no real title available?)
• A Fixed-Point Approach to Stable Matchings and Some Applications
• Algorithm Theory - SWAT 2004
• Algorithms and Computation
• Approximability results for stable marriage problems with ties.
• College Admissions and the Stability of Marriage
• Hard variants of stable marriage.
• Improved approximation of the stable marriage problem
• On the complexity of exchange-stable roommates
• Popular matchings
• Ramsey numbers and an approximation algorithm for the vertex cover problem
• Randomized approximation of the stable marriage problem
• STACS 2004
• Some remarks on the stable matching problem
• Stable marriage and indifference

Cited in

(17)

• Improved approximation of the stable marriage problem
• Approximating stable matchings with ties of bounded size
• The aviation technology two-sided matching with the expected time based on the probabilistic linguistic preference relations
• An $\frac{8}{5}$ -Approximation Algorithm for a Hard Variant of Stable Marriage
• Faster and simpler approximation of stable matchings
• Satisfied two-sided matching: a method considering elation and disappointment of agents
• A 1.875-approximation algorithm for the stable marriage problem
• Randomized approximation of the stable marriage problem
• Algorithm Theory - SWAT 2004
• A 25/17-approximation algorithm for the stable marriage problem with one-sided ties
• Randomized approximation of the stable marriage problem
• Approximation Algorithms for the Sex-Equal Stable Marriage Problem
• Approximation algorithms for the sex-equal stable marriage problem
• Improved approximation results for the stable marriage problem
• On the approximability of the stable matching problem with ties of size two
• Algorithms and Computation
• A 25/17-approximation algorithm for the stable marriage problem with one-sided ties

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

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