A 1.875: approximation algorithm for the stable marriage problem
A 1.875: approximation algorithm for the stable marriage problem
复制标题
DOI：
--
复制
发表时间：
2007-01
期刊：
影响因子：
--
通讯作者：
K. Iwama;S. Miyazaki;Naoya Yamauchi
中科院分区：
文献类型：
--
作者：
K. Iwama;S. Miyazaki;Naoya Yamauchi
我们考虑当优先列表中允许平局和不可接受的合作伙伴时找到最大尺寸的稳定匹配的问题。该问题被认为是 APX-hard 问题，当前最著名的近似算法实现了近似比率 2-c 1/√N，其中 c 是某个正常数。在本文中，我们给出了1.875近似算法，这是第一个在近似比上优于2的结果。
We consider the problem of finding a stable matching of maximum size when both ties and unacceptable partners are allowed in preference lists. This problem is known to be APX-hard, and the current best known approximation algorithm achieves the approximation ratio 2-c 1/√N, where c is some positive constant. In this paper, we give a 1.875-approximation algorithm, which is the first result on the approximation ratio better than two.