A (2-c1N)-approximation algorithm for the stable marriage problem
DOI10.1007/S00453-007-9101-YzbMATH Open1141.91301OpenAlexW2030655102MaRDI QIDQ930600FDOQ930600
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
Recommendations
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)
Cites Work
- Some remarks on the stable matching problem
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- College Admissions and the Stability of Marriage
- A Fixed-Point Approach to Stable Matchings and Some Applications
- Title not available (Why is that?)
- Algorithms and Computation
- Title not available (Why is that?)
- Ramsey numbers and an approximation algorithm for the vertex cover problem
- Title not available (Why is that?)
- Popular matchings
- Title not available (Why is that?)
- Title not available (Why is that?)
- Hard variants of stable marriage.
- Stable marriage and indifference
- Title not available (Why is that?)
- Randomized approximation of the stable marriage problem
- Title not available (Why is that?)
- Approximability results for stable marriage problems with ties.
- Title not available (Why is that?)
- Algorithm Theory - SWAT 2004
- On the complexity of exchange-stable roommates
- Title not available (Why is that?)
- STACS 2004
- Algorithms - ESA 2003
Cited In (10)
- 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
- Randomized approximation of the stable marriage problem
- Algorithm Theory - SWAT 2004
- Approximation Algorithms for the Sex-Equal Stable Marriage Problem
- 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)
