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/s10878-007-9133-x, 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 (SODA '07: Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 288-297, 2007). For the cases considered 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). Our algorithms not only give better approximation ratios than the cited ones, but are much simpler and run significantly faster. Also we may drop a restriction used in (J. Comb. Optim., doi: 10.1007/s10878-007-9133-x, 2007) and the analysis is substantially more moderate. Preliminary versions of this paper appeared in (Kiraly, Egres Technical Report TR-2008-04, www.cs.elte.hu/egres/, 2008; Kiraly in Proceedings of MATCH-UP 2008: Matching Under Preferences-Algorithms and Complexity, Satellite Workshop of ICALP, July 6, 2008, Reykjavik, Iceland, pp. 36-45, 2008; Kiraly in ESA 2008, Lecture Notes in Computer Science, vol. 5193, pp. 623-634, 2008). For the related results obtained thenceforth see Sect. 5.
approximation algorithms stable matching hospitals/residents problem