A natural family of optimization problems with arbitrarily small approximation thresholds

We give a concrete example of a family of natural graph-theoretic problems which behave better and better with respect to approximability but none of which are likely to admit a polynomial time approximation scheme. More specifically, the family exhibits problems with arbitrarily small, yet positive (assuming P ≠ NP), approximation thresholds. The family of problems we give is the independent set problem on k-iterated total graphs, ∀k ≥ 1. © 1998 Published by Elsevier Science B.V. All rights reserved.