The NP-Completeness Column: The Many Limits on Approximation

Abstract. This is the 25th edition of a column that covers new developments in the theory of NP-completeness. The presentation is modeled on that which M. R. Garey and I used in our book “Computers and Intractability: A Guide to the Theory of NP-Completeness, ” W. H. Freeman & Co., New York, 1979, hereinafter referred to as “[G&J]. ” Previous columns, the first 23 of which appeared in J. Algorithms, will be referred to by a combination of their sequence number and year of appearance, e.g., “[Col 1, 1981]. ” Full bibliographic details on the previous columns, as well as downloadable unofficial versions of them, can be found a