Characterization of a next generation step-and-scan system
Timothy J. Wiltshire, Joseph P. Kirk, et al.
SPIE Advanced Lithography 1998
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.
Timothy J. Wiltshire, Joseph P. Kirk, et al.
SPIE Advanced Lithography 1998
Martin Charles Golumbic, Renu C. Laskar
Discrete Applied Mathematics
Sankar Basu
Journal of the Franklin Institute
Richard M. Karp, Raymond E. Miller
Journal of Computer and System Sciences