PTAS definition vs. FPTAS

Question

From what I read in the preliminary version of a chapter of the book “Lectures on Scheduling” edited by R.H. M¨ohring, C.N. Potts, A.S. Schulz, G.J. Woeginger, L.A. Wolsey, to appear around 2011 A.D.

This is the PTAS Definition:

A polynomial time approximation scheme (PTAS) for problem $X$ is an approximation scheme whose time complexity is polynomial in the input size.

and FPTAS definition

A fully polynomial time approximation scheme (FPTAS) for problem $X$ is an approximation scheme whose time complexity is polynomial in the input size and also polynomial in 1/$\epsilon$.

Then the writer says:

Hence, for a PTAS it would be acceptable to have a time complexity proportional to $|I|^{1/\epsilon}$ where $|I|$ is the input size;although this time complexity is exponential in $1/\epsilon$. An FPTAS cannot have a time complexity that grows exponentially in $1/\epsilon$ but a time complexity proportional to $|I|^8/\epsilon^3$ would be fine. With respect to worst case approximation, an FPTAS is the strongest possible result that we can derive for an NP-hard problem.

Then he suggested the following figure to illustrates the relationships between the classes of problems:

Here is my questions:

1. From the PTAS and the FPTAS definition, how does the writer conclude that the FPTAS cannot have a time complexity that grows exponentially in $1/\epsilon$? and what difference does it make if it can have such time complexity?

2. A time complexity like $(n+1/\epsilon)^3$ is acceptable for FPTAS but it is not for PTAS, then why FPTAS is considered to be a subset of PTAS?

3. What does he mean by: an FPTAS is the strongest possible result that we can derive for an NP-hard problem.

4. In the aggregate I would like to know what exactly these to concepts mean and, what are their distinct properties.

Thanks in advance.

Answer 1

Let me answer your questions in order:

1. By definition, a problem has an FPTAS if there is an algorithm which on instances of length $n$ gives an $1+\epsilon$-approximation and runs in time polynomial in $n$ and $1/\epsilon$, that is $O((n/\epsilon)^C)$ for some constant $C \geq 0$. A running time of $2^{1/\epsilon}$ doesn't belong to $O((n/\epsilon)^C)$ for any $C$.
   An algorithm whose running time is $O((n/\epsilon)^C)$ is better than an algorithm whose running time is only guaranteed to be $O(n^C e^{D/\epsilon})$, since the dependency on $\epsilon$ is better for the first algorithm. Furthermore, for any $E$, we can find an $1+1/n^E$-approximation in polynomial time using the first algorithm but not using the second (at least not with the given guarantee).

2. A problem in which an $1+\epsilon$-approximation can be found in time $(n+1/\epsilon)^3$ is definitely in PTAS, since for every $\epsilon$ this is $O(n^3)$ (exercise) and so polynomial in $n$.

3. What the authors meant here is that since an NP-hard optimization problem can't be solved exactly in polynomial time, the best we can hope for is for it to be $\epsilon$-approximable in polynomial time, and furthermore with a good dependence on $\epsilon$. Among the common complexity classes, FPTAS gives the strongest guarantee on the dependence on $\epsilon$. But in practice we sometimes get an even better guarantee: the running time is polynomial in $n$ and in $\log(1/\epsilon)$. So it's not strictly true that FPTAS is the strongest possible result; it's only the strongest possible result among the options PTAS,FPTAS,P. If we made up a new class LPTAS (corresponding to time polynomial in $n$ and in $\log(1/\epsilon)$), then that would be a stronger guarantee.

4. Given an NP-hard optimization problem, it can't be solved exactly in polynomial time; the best one can hope for is to approximate it efficiently. Some problems are NP-hard to approximate to some constant $C>1$. For others, it is possible to approximate the problem arbitrarily well in polynomial time, and these problems have a PTAS and so belong to the class PTAS. It might be that a $1+\epsilon$-approximation takes time proportional to $e^{1/\epsilon}$, and so we can only apply this efficiently for constant $\epsilon$. If the problem has an FPTAS (and so belongs to the class FPTAS), then we know that the dependency on $\epsilon$ is only polynomial, and so we can approximate efficiently to within $1+1/n^C$ for any $C$.

Answer 2

Let the instance size be $|I|=n$. The difference between a PTAS and an FPTAS is that, in the former $\epsilon$ is a fixed constant, so that it can be treated as a constant. That is why a running time such as $n^{1/\epsilon}$ is still polynomial in instance size $n$ (also in input size as $\epsilon$ is a fixed constant anyway). In an FPTAS, $\epsilon$ is not fixed. The approximation scheme must be polynomial in $1/\epsilon$ as well as $n$ (ie, $\mathrm{poly}(n,1/\epsilon)$ as in $n^4 (1/\epsilon)^3 + (1/\epsilon)^8$). A running time such as $n^{1/\epsilon}$ is clearly not polynomial in $n$ and $1/\epsilon$. Hence such an approximation scheme is a PTAS but not an FPTAS.