# Meaning behind 1/ϵ in FPTAS

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?

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

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.