Sonia Cafieri, Jon Lee, et al.
Journal of Global Optimization
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). © 2012 Springer Science+Business Media New York.
Sonia Cafieri, Jon Lee, et al.
Journal of Global Optimization
David W. Jacobs, Daphna Weinshall, et al.
IEEE Transactions on Pattern Analysis and Machine Intelligence
Paul J. Steinhardt, P. Chaudhari
Journal of Computational Physics
David L. Shealy, John A. Hoffnagle
SPIE Optical Engineering + Applications 2007