Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR97-001 | 8th January 1997 00:00

On the Efficiency of Polynomial Time Approximation Schemes


Authors: Marco Cesati, Luca Trevisan
Publication: 21st January 1997 20:11
Downloads: 4032


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.

ISSN 1433-8092 | Imprint