Just to get the current terminology straight after yesterday's class.


a PTAS, polynomial time approximation scheme, is an algorithm that
finds a solution within (1+ epsilon) of optimal, in time polynomial in
n, for any fixed epsilon.

an FPTAS, fully polynomial time approximation scheme, is an algorithm that
finds a solution within (1+ epsilon) of optimal, in  time polynomail
in n and 1/epsilon


If a problem is strongly NP-hard, and its objective function takes on
integer values, then no FPTAS is possible (this is proved in Garey and
Johnson).


There are also many problems for which it has been proved that no PTAS
is possible.  This is typically done in one of two ways:
1) via the new characterization of NP via PCP (probabilistically
checkable proofs), 
2) by proving that for some fixed k, it is NP-hard to determine if
there is a solution of value < k.  This implies a lower bound of
(k+1)/k on the approximation ratio.

(many thanks to Cliff, who clarified this for us!)