TY - JOUR
T1 - Improved approximation results for the stable marriage problem
AU - Halldórsson, Magnús M.
AU - Iwama, Kazuo
AU - Miyazaki, Shuichi
AU - Yanagisawa, Hiroki
PY - 2007/8/1
Y1 - 2007/8/1
N2 - The stable marriage problem has recently been studied in its general setting, where both ties and incomplete lists are allowed. It is NP-hard to find a stable matching of maximum size, while any stable matching is a maximal matching and thus trivially we can obtain a 2-approximation algorithm. In this article, we give the first nontrivial result for approximation of factor less than two. Our algorithm achieves an approximation ratio of 2/(1 + L -2) for instances in which only men have ties of length at most L. When both men and women are allowed to have ties but the lengths are limited to two, then we show a ratio of 13/7(<1.858). We also improve the lower bound on the approximation ratio to 21/19(>1.1052).
AB - The stable marriage problem has recently been studied in its general setting, where both ties and incomplete lists are allowed. It is NP-hard to find a stable matching of maximum size, while any stable matching is a maximal matching and thus trivially we can obtain a 2-approximation algorithm. In this article, we give the first nontrivial result for approximation of factor less than two. Our algorithm achieves an approximation ratio of 2/(1 + L -2) for instances in which only men have ties of length at most L. When both men and women are allowed to have ties but the lengths are limited to two, then we show a ratio of 13/7(<1.858). We also improve the lower bound on the approximation ratio to 21/19(>1.1052).
KW - Approximation algorithms
KW - Incomplete lists
KW - Stable marriage problem
KW - Ties
UR - http://www.scopus.com/inward/record.url?scp=34548286312&partnerID=8YFLogxK
U2 - 10.1145/1273340.1273346
DO - 10.1145/1273340.1273346
M3 - Article
AN - SCOPUS:34548286312
SN - 1549-6325
VL - 3
JO - ACM Transactions on Algorithms
JF - ACM Transactions on Algorithms
IS - 3
M1 - 1273346
ER -