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 spec ifically, the family exhibits problems with arbitrarily small, yet positive (assuming P not equal NP), approximation thresholds. The family of problem s we give is the independent set problem on k-iterated total graphs, For Al l k greater than or equal to 1. (C) 1998 Published by Elsevier Science B.V. All rights reserved.