### M. Cesati, L. Trevisan, ``On the Efficiency of Polynomial
Time Approximation Schemes'', Information Processing Letters,
64(47) 165-171, 1997, Elsevier.

A polynomial time approximation scheme (PTAS) for an
optimization problem A is an algorithm that on input an
instance of A and e > 0 finds a (1+e)-approximate solution
in time that is polynomial for each fixed e. Typical running
times are n^{O(1/e} or 2^{1/e^{O(1)}} n. While algorithms of
the former kind tend to be impractical, the latter ones are
more interesting. In several cases, the development of
algorithms of the second type required considerably new (and
sometimes harder) techniques. For some interesting problems
(including Euclidean TSP) only an
n^{O(1/e)} approximation scheme is known. Under likely
assumptions, we prove that for some problems (including natural
ones) there cannot be approximation schemes running in time
f(1/e) n^{O(1)}, no matter how fast function f() grows. Our
result relies on a connection with Parameterized Complexity
Theory. We show that this connection is necessary.

[PostScript] [PDF]

Back to the Marco
Cesati's research page.