Better and Simpler Approximation Algorithms for the Stable Marriage Problem

摘要

We first consider the problem of finding a maximum size stable matching if incomplete lists and ties are both allowed, but ties are on one side only. For this problem we give a simple, linear time 3/2-approximation algorithm, improving on the best known approximation factor 5/3 of Irving and Manlove (J. Comb. Optim., doi:10.1007/sl0878-007-9133-x, 2007). Next, we show how this extends to the Hos pitals/Residents problem with the same ratio if the residents have strict orders. We also give a simple linear time algorithm for the general problem with approxima tion factor 5/3, improving the best known 15/8-approximation algorithm of Iwama, Miyazaki and Yamauchi (SODA '07: Proceedings of the Eighteenth Annual ACM SIAM Symposium on Discrete Algorithms, pp. 288-297, 2007). For the cases con sidered in this paper it is NP-hard to approximate within a factor of 21/19 by the result of Halldorsson et al. (ACM Transactions on Algorithms 3(3):30, 2007).