Improved approximation of the stable marriage problem

DOI10.1007/B13632zbMATH Open1266.05173OpenAlexW1827234103MaRDI QIDQ5897252FDOQ5897252

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

Publication date: 3 March 2010

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

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

Recommendations

• Improved approximation results for the stable marriage problem
• 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
• Better and simpler approximation algorithms for the stable marriage problem

zbMATH Keywords

tiesstable marriage problemstable matching

Mathematics Subject Classification ID

Approximation algorithms (68W25) Transversal (matching) theory (05D15)

Cited In (19)

• Approximating stable matchings with ties of bounded size
• A \((2-c\frac{1}{\sqrt{N}})\)-approximation algorithm for the stable marriage problem
• Stable marriage with ties and bounded length preference lists
• An improved approximation lower bound for finding almost stable maximum matchings
• A tight approximation bound for the stable marriage problem with restricted ties
• Linear time local approximation algorithm for maximum stable marriage
• A \(1.875\)-approximation algorithm for the stable marriage problem
• An improved approximation algorithm for the stable marriage problem with one-sided ties
• Randomized approximation of the stable marriage problem
• Approximability results for stable marriage problems with ties.
• Algorithm Theory - SWAT 2004
• Better and simpler approximation algorithms for the stable marriage problem
• Randomized approximation of the stable marriage problem
• A 3/2-Approximation Algorithm for General Stable Marriage
• Improved approximation algorithms for two variants of the stable marriage problem with ties
• Title not available (Why is that?)
• Improved approximation results for the stable marriage problem
• Better and Simpler Approximation Algorithms for the Stable Marriage Problem
• Approximation algorithms for hard variants of the stable marriage and hospitals/residents problems

This page was built for publication: Improved 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 Q5897252)