An \frac{8}{5} -Approximation Algorithm for a Hard Variant of Stable Marriage

DOI10.1007/978-3-540-73545-8_53zbMATH Open1213.68707OpenAlexW1601434077MaRDI QIDQ3608878FDOQ3608878

Robert W. Irving, David F. Manlove

Publication date: 6 March 2009

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-73545-8_53

Recommendations

• A \(1.875\)-approximation algorithm for the stable marriage problem
• Hardness and approximation results for some variants of stable marriage problem
• A \((2-c\frac{1}{\sqrt{N}})\)-approximation algorithm for the stable marriage problem
• Algorithms and Computation
• Better and simpler approximation algorithms for the stable marriage problem
• Better and Simpler Approximation Algorithms for the Stable Marriage Problem
• A 3/2-Approximation Algorithm for General Stable Marriage
• Algorithm Theory - SWAT 2004
• Randomized approximation of the stable marriage problem
• Randomized approximation of the stable marriage problem

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Combinatorics in computer science (68R05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Cited In (2)

• Hard variants of stable marriage.
• Approximation algorithms for hard variants of the stable marriage and hospitals/residents problems

This page was built for publication: An $\frac{8}{5}$ -Approximation Algorithm for a Hard Variant of Stable Marriage

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