Faster and simpler approximation of stable matchings

DOI10.3390/a7020189zbMath1461.68259OpenAlexW2019340823MaRDI QIDQ1736612

Katarzyna E. Paluch

Publication date: 26 March 2019

Published in: Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.3390/a7020189

zbMATH Keywords

approximation algorithmstable matchingstable marriage

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25) Matching models (91B68)

Related Items (7)

Characterization of super-stable matchings ⋮ Hardness and approximation results for some variants of stable marriage problem ⋮ On the approximability of the stable matching problem with ties of size two ⋮ Collapsing Superstring Conjecture ⋮ Mathematical models for stable matching problems with ties and incomplete lists ⋮ Unnamed Item ⋮ Maximum stable matching with one-sided ties of bounded length

Cites Work

• Better and simpler approximation algorithms for the stable marriage problem
• A \((2-c\frac{1}{\sqrt{N}})\)-approximation algorithm for the stable marriage problem
• Approximability results for stable marriage problems with ties.
• Hard variants of stable marriage.
• Faster and Simpler Approximation of Stable Matchings
• Improved approximation results for the stable marriage problem
• A 25/17-Approximation Algorithm for the Stable Marriage Problem with One-Sided Ties
• Approximation Algorithms for the Sex-Equal Stable Marriage Problem
• A 3/2-Approximation Algorithm for General Stable Marriage
• Finding large stable matchings
• College Admissions and the Stability of Marriage
• Unnamed Item
• Unnamed Item

This page was built for publication: Faster and simpler approximation of stable matchings