Randomized approximation of the stable marriage problem

DOI10.1007/3-540-45071-8_35zbMATH Open1276.68173OpenAlexW4243054930MaRDI QIDQ3082941FDOQ3082941

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

Publication date: 18 March 2011

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

Full work available at URL: https://doi.org/10.1007/3-540-45071-8_35

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

Mathematics Subject Classification ID

Randomized algorithms (68W20) Approximation algorithms (68W25) Matching models (91B68)

Cited In (7)

• An $\frac{8}{5}$ -Approximation Algorithm for a Hard Variant of Stable Marriage
• Randomized approximation of the stable marriage problem
• Distributed Weighted Stable Marriage Problem
• Progress in Cryptology - INDOCRYPT 2004
• Local search approaches in stable matching problems
• Efficient algorithms for generalized stable marriage and roommates problems
• Algorithms and Computation

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 Q3082941)