Back to Search
Start Over
Better and Simpler Approximation Algorithms for the Stable Marriage Problem.
- Source :
- Algorithmica; May2011, Vol. 60 Issue 1, p3-20, 18p
- Publication Year :
- 2011
-
Abstract
- 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:, ). 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, ). 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. (ACM Transactions on Algorithms 3(3):30, ). 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:, ) and the analysis is substantially more moderate. Preliminary versions of this paper appeared in (Király, Egres Technical Report TR-2008-04, , ; Király in Proceedings of MATCH-UP 2008: Matching Under Preferences-Algorithms and Complexity, Satellite Workshop of ICALP, July 6, 2008, Reykjavík, Iceland, pp. 36-45, ; Király in ESA 2008, Lecture Notes in Computer Science, vol. 5193, pp. 623-634, ). For the related results obtained thenceforth see Sect. 5. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 01784617
- Volume :
- 60
- Issue :
- 1
- Database :
- Complementary Index
- Journal :
- Algorithmica
- Publication Type :
- Academic Journal
- Accession number :
- 58664235
- Full Text :
- https://doi.org/10.1007/s00453-009-9371-7