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

DOI10.1137/1.9781611975482.175MaRDI QIDQ5236366zbMATH OpenOpenAlexFDO

Authors Chi-Kit Lam, C. G. Plaxton

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

Mathematics Subject Classification ID

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

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

Cited in

(7)

• Characterization of super-stable matchings
• Maximum stable matching with one-sided ties of bounded length
• 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)