2
$\begingroup$

I am currently learning about FPTAS and PTAS but do not understand what the definition of FPTAS.

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

In this explanation, what does the $\epsilon$ stand for?

$\endgroup$
  • 4
    $\begingroup$ The answer is probably just outside that quotation. Which source are you using? You need to credit it! $\endgroup$ – Raphael Jun 19 '16 at 18:06
5
$\begingroup$

Suppose that your problem is a minimization problem: on instance $I$, you output a solution $O$ which should minimize some function $f(O)$. We say that an algorithm is a $(1+\epsilon)$-approximation if on instance $I$ it outputs a solution $S$ which satisfies $$ f(S) \leq (1+\epsilon) f(O) $$ for an optimal solution $O$. We also say that $S$ is a $(1+\epsilon)$-approximate solution.

An FPTAS is an algorithm that gets as input an instance of size $n$ and a number $\epsilon>0$ (let's not worry about how $\epsilon$ is represented), returns a $(1+\epsilon)$-approximate solution, and runs in time $O(n^C (1/\epsilon)^D)$ for some constants $C,D>0$.

Given an FPTAS, you can extract a polynomial time $(1+\epsilon)$-approximation algorithm for any $\epsilon > 0$; furthermore, the dependence of the running time on $\epsilon$ is polynomial (in $1/\epsilon$).

A PTAS, in contrast, is an algorithm gets as input an instance of size $n$ and a number $\epsilon>0$, returns a $(1+\epsilon)$-approximate solution, and for any fixed $\epsilon > 0$, runs in polynomial time. That is, for every $\epsilon > 0$ there exist constants $A_\epsilon,C_\epsilon$ such that the running time of the algorithm is at most $A_\epsilon n^{C_\epsilon}$.

Again, given a PTAS, for any $\epsilon > 0$ we can extract a polynomial time $(1+\epsilon)$-approximation algorithm. This time, however, the dependence of the running time on $\epsilon$ can be arbitrary.

$\endgroup$

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.