Randomized approximation of the stable marriage problem

DOI10.1016/J.TCS.2004.02.045MaRDI QIDQ1884845zbMATH OpenOpenAlexFDO

Authors Magnús M. Halldórsson, Kazuo Iwama, Shuichi Miyazaki, Hiroki Yanagisawa

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) Randomized algorithms (68W20) Approximation algorithms (68W25) Transversal (matching) theory (05D15)

Recommendations

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

Cites work

• scientific article; zbMATH DE number 1617265 (Why is no real title available?)
• scientific article; zbMATH DE number 2086256 (Why is no real title available?)
• scientific article; zbMATH DE number 45086 (Why is no real title available?)
• scientific article; zbMATH DE number 1512672 (Why is no real title available?)
• scientific article; zbMATH DE number 1405659 (Why is no real title available?)
• scientific article; zbMATH DE number 1445320 (Why is no real title available?)
• College Admissions and the Stability of Marriage
• Edge Dominating Sets in Graphs
• Hard variants of stable marriage.
• Improved approximation of the stable marriage problem
• Ramsey numbers and an approximation algorithm for the vertex cover problem
• Some remarks on the stable matching problem
• Stable marriage and indifference

Cited in

(19)

• A \((2-c\frac{1}{\sqrt{N}})\)-approximation algorithm for the stable marriage problem
• Stable marriage with ties and bounded length preference lists
• An $\frac{8}{5}$ -Approximation Algorithm for a Hard Variant of Stable Marriage
• Linear time local approximation algorithm for maximum stable marriage
• Satisfied two-sided matching: a method considering elation and disappointment of agents
• Maximum stable matching with one-sided ties of bounded length
• Better and simpler approximation algorithms for the stable marriage problem
• Distributed Weighted Stable Marriage Problem
• Randomized approximation of the stable marriage problem
• Research and development of fringe projection-based methods in 3D shape reconstruction
• Improved approximation algorithms for two variants of the stable marriage problem with ties
• Progress in Cryptology - INDOCRYPT 2004
• Better and Simpler Approximation Algorithms for the Stable Marriage Problem
• Approximation algorithms for hard variants of the stable marriage and hospitals/residents problems
• Efficient algorithms for generalized stable marriage and roommates problems
• Review of the theory of stable matchings and contract systems
• Algorithms and Computation
• A 25/17-approximation algorithm for the stable marriage problem with one-sided ties
• Randomized $\tilde{O}(M(|V|))$ Algorithms for Problems in Matching Theory

This page was built for publication: Randomized approximation of the stable marriage problem

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