A (1 + 1/e)-Approximation Algorithm for Maximum Stable Matching with One-Sided Ties and Incomplete Lists

DOI10.1137/1.9781611975482.175zbMath1432.68579OpenAlexW4232291999MaRDI QIDQ5236366

C. Gregory 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

Mathematics Subject Classification ID

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

Related Items (3)

Characterization of super-stable matchings ⋮ On the approximability of the stable matching problem with ties of size two ⋮ Maximum stable matching with one-sided ties of bounded length

This page was built for publication: A (1 + 1/e)-Approximation Algorithm for Maximum Stable Matching with One-Sided Ties and Incomplete Lists