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

DOI10.1007/978-3-540-73545-8_53MaRDI QIDQ3608878zbMATH OpenOpenAlexFDO

Authors 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

Mathematics Subject Classification ID

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

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

Cited in

(3)

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

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)