Algorithm Theory - SWAT 2004

DOI10.1007/B98413MaRDI QIDQ5315387zbMATH OpenOpenAlexFDO

Authors Shuichi Miyazaki, Kazuya Okamoto, Kazuo Iwama

Publication date 7 September 2005

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

Full work available at URL https://doi.org/10.1007/b98413

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Transversal (matching) theory (05D15) Approximation algorithms (68W25) Matching models (91B68)

Recommendations

• Algorithms and Computation
• A \((2-c\frac{1}{\sqrt{N}})\)-approximation algorithm for the stable marriage problem
• A 1.875-approximation algorithm for the stable marriage problem
• Improved approximation of the stable marriage problem
• Improved approximation results for the stable marriage problem

Cited in

(12)

• Stable marriage with ties and bounded length preference lists
• Approximation algorithms for hard variants of the stable marriage and hospitals/residents problems
• Local search approaches in stable matching problems
• Almost stable matchings by truncating the Gale-Shapley algorithm
• The stable marriage problem: an interdisciplinary review from the physicist's perspective
• Faster and simpler approximation of stable matchings
• A 1.875-approximation algorithm for the stable marriage problem
• An $\frac{8}{5}$ -Approximation Algorithm for a Hard Variant of Stable Marriage
• A 3/2-Approximation Algorithm for General Stable Marriage
• Algorithms and Computation
• Stable multi-skill workforce assignments
• A \((2-c\frac{1}{\sqrt{N}})\)-approximation algorithm for the stable marriage problem

This page was built for publication: Algorithm Theory - SWAT 2004

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