A 25/17-Approximation Algorithm for the Stable Marriage Problem with One-Sided Ties

摘要

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).