Randomized approximation of the stable marriage problem

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

zbMATH Keywords

Approximation algorithmsTiesIncomplete listsStable marriage problem

Mathematics Subject Classification ID

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