TR97-001 Authors: Marco Cesati, Luca Trevisan

Publication: 21st January 1997 20:11

Downloads: 2541

Keywords:

A polynomial time approximation scheme (PTAS) for an optimization

problem $A$ is an algorithm that on input an instance of $A$ and

$\epsilon > 0$ finds a $(1+\epsilon)$-approximate solution in time

that is polynomial for each fixed $\epsilon$. Typical running times

are $n^{O(1/\epsilon)}$ or $2^{1/\epsilon^{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/\epsilon)}$ 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/\epsilon) 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.