Article ID: | iaor20112707 |
Volume: | 60 |
Issue: | 1 |
Start Page Number: | 3 |
End Page Number: | 20 |
Publication Date: | May 2011 |
Journal: | Algorithmica |
Authors: | Kirly Zoltn |
Keywords: | matching |
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 (2007). Next, we show how this extends to the Hospitals/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 approximation factor 5/3, improving the best known 15/8-approximation algorithm of Iwama, Miyazaki and Yamauchi (2007). For the cases considered in this paper it is NP-hard to approximate within a factor of 21/19 by the result of Halldórsson et al. (2007). Our algorithms not only give better approximation ratios than the cited ones, but are much simpler and run significantly faster.