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 algorithmsIncomplete listsThe stable marriage problemTies

Mathematics Subject Classification ID

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

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

• 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
• Gale-Shapley stable marriage problem revisited: Strategic issues and applications. (Extended abstract)
• Hard variants of stable marriage.
• 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 1962834 (Why is no real title available?)
• scientific article; zbMATH DE number 2038736 (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?)
• Improved approximation of the stable marriage problem
• Induced matchings in regular graphs and trees
• Matching medical students to pairs of hospitals: A new variation on a well-known theme
• 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
• Some remarks on the stable matching problem
• Stable marriage and indifference
• Stable marriage with incomplete lists and ties
• STACS 2004
• The hospitals/residents problem with ties

Cited in

(17)

• Satisfied two-sided matching: a method considering elation and disappointment of agents
• Faster and simpler approximation of stable matchings
• Randomized 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
• On the approximability of the stable matching problem with ties of size two
• A 1.875-approximation algorithm for the stable marriage problem
• Randomized approximation of the stable marriage problem
• Approximation algorithms for the sex-equal stable marriage problem
• Improved approximation results for the stable marriage problem
• A 25/17-approximation algorithm for the stable marriage problem with one-sided ties
• Approximation Algorithms for the Sex-Equal Stable Marriage Problem
• An $\frac{8}{5}$ -Approximation Algorithm for a Hard Variant of Stable Marriage
• A 25/17-approximation algorithm for the stable marriage problem with one-sided ties
• Algorithm Theory - SWAT 2004
• Improved approximation of the stable marriage problem
• Algorithms and Computation

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)