A 25/17-Approximation Algorithm for the Stable Marriage Problem with One-Sided Ties
A 25/17-Approximation Algorithm for the Stable Marriage Problem with One-Sided Ties
复制标题
一种解决单边关系稳定婚姻问题的 25/17 近似算法
DOI：
10.1007/s00453-012-9699-2
复制
发表时间：
2014
期刊：
影响因子：
1.1
通讯作者：
and Hiroki Yanagisawa
中科院分区：
文献类型：
--
作者：
Kazuo Iwama;Shuichi Miyazaki;and Hiroki Yanagisawa
寻找最大稳定匹配的问题，其中偏好列表可能包括领带和不可接受的合作伙伴（MAX SMTI）是已知的NP-难。除非P=NP，否则它不能在33/29（>1.1379）内近似，而目前的最佳近似算法达到了1.5的比率。即使当一方的偏好列表不包含领带时，MAX SMTI仍然是NP难的，并且除非P=NP，否则它不能在21/19（>1.1052）内近似。然而，即使在这种限制下，最好的近似比仍然是1.5。本文将其改进为25/17（<1.4706）。
The problem of finding a largest stable matching where preference lists may include ties and unacceptable partners (MAX SMTI) is known to be NP-hard. It cannot be approximated within 33/29 (>1.1379) unless P=NP, and the current best approximation algorithm achieves the ratio of 1.5. MAX SMTI remains NP-hard even when preference lists of one side do not contain ties, and it cannot be approximated within 21/19 (>1.1052) unless P=NP. However, even under this restriction, the best known approximation ratio is still 1.5. In this paper, we improve it to 25/17 (<1.4706).