Randomized approximation of the stable marriage problem
Randomized approximation of the stable marriage problem
复制标题
DOI：
10.1016/j.tcs.2004.02.045
复制
发表时间：
2003-07
期刊：
影响因子：
--
通讯作者：
M. Halldórsson;K. Iwama;S. Miyazaki;H. Yanagisawa
中科院分区：
文献类型：
--
作者：
M. Halldórsson;K. Iwama;S. Miyazaki;H. Yanagisawa
虽然最初的稳定婚姻问题要求所有参与者按照严格的顺序对所有异性成员进行排名，但有两个自然变化，即允许不完整的偏好列表和偏好之间的联系。这两种变化都是多项式可解的，但最近发现当这两种变化都被允许时，寻找最大基数稳定匹配是NP-困难的。很容易看出，任何两个稳定匹配的大小最多相差2倍，因此，具有2倍的近似算法是微不足道的。本文给出了一个随机近似算法RANDBRK，并证明了它对于受限但仍是NP-难的情形的期望近似比至多为10/7(<；1.4286)，其中领带只出现在男士列表中，每个男士最多写一条领带，领带的长度为两条。我们还通过给出RANDBRK的下界32/23(>；1.3913)来证明我们的分析几乎是紧的。此外，我们还证明了除了最后一个限制外，这些限制都可以在不增加太多近似比的情况下被消除。
While the original stable marriage problem requires all participants to rank all members of the opposite sex in a strict order, two natural variations are to allow for incomplete preference lists and ties in the preferences. Either variation is polynomially solvable, but it has recently been shown to be NP-hard to find a maximum cardinality stable matching when both of the variations are allowed. It is easy to see that the size of any two stable matchings differ by at most a factor of two, and so, an approximation algorithm with a factor two is trivial. In this paper, we give a randomized approximation algorithm RANDBRK and show that its expected approximation ratio is at most 10/7(<1.4286) for a restricted but still NP-hard case, where ties occur in only men's lists, each man writes at most one tie, and the length of ties is two. We also show that our analysis is nearly tight by giving a lower bound 32/23(>1.3913) for RANDBRK. Furthermore, we show that these restrictions except for the last one can be removed without increasing the approximation ratio too much.