Improved approximation results for the stable marriage problem

DOI10.1145/1273340.1273346zbMATH Open1192.68903OpenAlexW2071503214MaRDI QIDQ3580942FDOQ3580942

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

Publication date: 14 August 2010

Published in: ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1273340.1273346

Recommendations

• Improved approximation of 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

Mathematics Subject Classification ID

Combinatorics in computer science (68R05) Nonnumerical algorithms (68W05) Approximation algorithms (68W25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Matching models (91B68)

Cited In (34)

• Approximating stable matchings with ties of bounded size
• The hospitals/residents problem with lower quotas
• A \((2-c\frac{1}{\sqrt{N}})\)-approximation algorithm for the stable marriage problem
• Stable Matching with Uncertain Linear Preferences
• Improved approximation bounds for the student-project allocation problem with preferences over projects
• An improved approximation lower bound for finding almost stable maximum matchings
• A tight approximation bound for the stable marriage problem with restricted ties
• Faster and simpler approximation of stable matchings
• Linear time local approximation algorithm for maximum stable marriage
• A \(1.875\)-approximation algorithm for the stable marriage problem
• Maximum stable matching with one-sided ties of bounded length
• Maximum locally stable matchings
• Randomized approximation of the stable marriage problem
• Approximability results for stable marriage problems with ties.
• Stable matching with uncertain linear preferences
• Algorithm Theory - SWAT 2004
• Improved approximation bounds for the student-project allocation problem with preferences over projects
• 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
• Envy-freeness and relaxed stability: hardness and approximation algorithms
• Local search approaches in stable matching problems
• Critical Relaxed Stable Matchings with Two-Sided Ties
• Approximability of economic equilibrium for housing markets with duplicate houses
• Better and Simpler Approximation Algorithms for the Stable Marriage Problem
• Stable marriage with general preferences
• On the approximability of the stable matching problem with ties of size two
• Cutoff stability under distributional constraints with an application to summer internship matching
• Review of the theory of stable matchings and contract systems
• Mathematical models for stable matching problems with ties and incomplete lists
• Algorithms and Computation
• Improved approximation of the stable marriage problem
• A 25/17-approximation algorithm for the stable marriage problem with one-sided ties

This page was built for publication: Improved approximation results for the stable marriage problem

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