PTAS definition vs. FPTAS

ignougroup
Problem Detail: 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: enter image description here 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.

Asked By : Drupalist

Answered By : Yuval Filmus

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 polynomials, and so we can approximate efficiently to within $1+1/n^C$ for any $C$.
Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/51495