Randomized approximation of the stable marriage problem
From MaRDI portal
Publication:1884845
DOI10.1016/j.tcs.2004.02.045zbMath1071.68080OpenAlexW1999336648MaRDI QIDQ1884845
Kazuo Iwama, Magnús M. Halldórsson, Hiroki Yanagisawa, Shuichi Miyazaki
Publication date: 27 October 2004
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2004.02.045
Combinatorics in computer science (68R05) Transversal (matching) theory (05D15) Approximation algorithms (68W25) Randomized algorithms (68W20)
Related Items (12)
Satisfied two-sided matching: a method considering elation and disappointment of agents ⋮ Review of the theory of stable matchings and contract systems ⋮ Improved approximation algorithms for two variants of the stable marriage problem with ties ⋮ Better and Simpler Approximation Algorithms for the Stable Marriage Problem ⋮ A \((2-c\frac{1}{\sqrt{N}})\)-approximation algorithm for the stable marriage problem ⋮ Linear time local approximation algorithm for maximum stable marriage ⋮ A 25/17-approximation algorithm for the stable marriage problem with one-sided ties ⋮ Better and simpler approximation algorithms for the stable marriage problem ⋮ Research and development of fringe projection-based methods in 3D shape reconstruction ⋮ Maximum stable matching with one-sided ties of bounded length ⋮ Stable marriage with ties and bounded length preference lists ⋮ Approximation algorithms for hard variants of the stable marriage and hospitals/residents problems
Cites Work
- 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
- Hard variants of stable marriage.
- Edge Dominating Sets in Graphs
- Algorithms - ESA 2003
- College Admissions and the Stability of Marriage
This page was built for publication: Randomized approximation of the stable marriage problem
