Optimization of real phase-mask performance
F.M. Schellenberg, M. Levenson, et al.
BACUS Symposium on Photomask Technology and Management 1991
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.
F.M. Schellenberg, M. Levenson, et al.
BACUS Symposium on Photomask Technology and Management 1991
Robert F. Gordon, Edward A. MacNair, et al.
WSC 1985
A.R. Conn, Nick Gould, et al.
Mathematics of Computation
Yi Zhou, Parikshit Ram, et al.
ICLR 2023