Published in:
Algorithms - ESA 2008, Lecture Notes in Computer Science Volume 5193, 2008, pp 623-634
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 [5]. 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 [8]. 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. [3].
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 [5] and the analysis is substantially more moderate.
Preliminary versions of this paper appeared in [9, 10, 11]. For the related
results obtained thenceforth see Section 5.
Bibtex entry:
@techreport{egres-08-04,
AUTHOR | = | {Kir{\'a}ly, Zolt{\'a}n}, |
TITLE | = | {Better and simpler approximation algorithms for the stable marriage problem}, |
NOTE | = | {{\tt egres.elte.hu}}, |
INSTITUTION | = | {Egerv{\'a}ry Research Group, Budapest}, |
YEAR | = | {2008}, |
NUMBER | = | {TR-2008-04} |