Better and Simpler Approximation Algorithms for the Stable Marriage Problem

Better and Simpler Approximation Algorithms for the Stable Marriage Problem

0.00 Avg rating0 Votes
Article ID: iaor20112707
Volume: 60
Issue: 1
Start Page Number: 3
End Page Number: 20
Publication Date: May 2011
Journal: Algorithmica
Authors:
Keywords: matching
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 (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.

Reviews

Required fields are marked *. Your email address will not be published.