A (1 + 1/e)-approximation algorithm for maximum stable matching with one-sided ties and incomplete lists

DOI10.1137/1.9781611975482.175zbMATH Open1432.68579OpenAlexW4232291999MaRDI QIDQ5236366FDOQ5236366

C. G. Plaxton, Chi-Kit Lam

Publication date: 15 October 2019

Published in: Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/1.9781611975482.175

Recommendations

• Maximum stable matching with one-sided ties of bounded length
• A 25/17-approximation algorithm for the stable marriage problem with one-sided ties
• Maximum stable matching with one-sided ties of bounded length
• A 25/17-approximation algorithm for the stable marriage problem with one-sided ties
• An improved approximation algorithm for the stable marriage problem with one-sided ties

Mathematics Subject Classification ID

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

Cited In (6)

• Characterization of super-stable matchings
• Maximum stable matching with one-sided ties of bounded length
• Critical Relaxed Stable Matchings with Two-Sided Ties
• On the approximability of the stable matching problem with ties of size two
• Parameterized algorithms for stable matching with ties and incomplete lists
• Stable matchings, one-sided ties, and approximate popularity

This page was built for publication: A \((1 + 1/e)\)-approximation algorithm for maximum stable matching with one-sided ties and incomplete lists

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