11
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Where do you get that "A time complexity like $(n+1/\epsilon)^3$ is acceptable for FPTAS but it is not for PTAS"? ​ ​ $\endgroup$ – user12859 Jan 5 '16 at 15:05
  • 1
    $\begingroup$ Do not post more than one question in one post, please. It's quite possible that understanding an answer to your first question makes the rest follow. (Imho, your problem is that you don't understand what "and also polynomial in 1/ϵ" means.) $\endgroup$ – Raphael Jan 5 '16 at 17:18
  • $\begingroup$ @RickyDemer by its definition: its time complexity is polynomial in the input size (it means $n$) $\endgroup$ – M a m a D Jan 6 '16 at 6:04
  • $\begingroup$ ... ​ ​ $(n+1/\epsilon)^3$ ​ is polynomial in $n$ ​ ​ ​ ​ $\endgroup$ – user12859 Jan 6 '16 at 6:16
  • $\begingroup$ @RickyDemer you are right, I made mistake. Thank you. $\endgroup$ – M a m a D Jan 6 '16 at 6:17
13
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ Please do not encourage undesirable posting behaviour. $\endgroup$ – Raphael Jan 5 '16 at 17:18
1
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ Welcome to the site! I think it's rather misleading to claim that $\epsilon$ is a constant in a PTAS. The whole point of it being an approximation scheme rather than just an $\epsilon$-approximation is that it works for all $\epsilon$. $\epsilon$ is still a variable; it's just that we don't require the running time to be polynomial in $1/\epsilon$. $\endgroup$ – David Richerby Oct 2 '17 at 7:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.