V. Guruswami et Cp. Rangan, A natural family of optimization problems with arbitrarily small approximation thresholds, INF PROCESS, 68(5), 1998, pp. 241-248
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.