Difference Between PTAS and FPTAS According to this link:


  Polynomial Time Approximation Scheme (PTAS) is a type of approximate
  algorithms that provide user to control over accuracy which is a
  desirable feature. These algorithms take an additional parameter ε > 0
  and provide a solution that is (1 + ε) approximate for minimization
  and (1 – ε) for maximization. For example consider a minimization
  problem, if ε is 0.5, then the solution provided by the PTAS algorithm
  is 1.5 approximate. The running time of PTAS must be polynomial in
  terms of n, however, it can be exponential in terms of ε.
  
  In PTAS algorithms, the exponent of the polynomial can increase
  dramatically as ε reduces, for example if the runtime is O(n(1/ε)!)
  which is a problem. There is a stricter scheme, Fully Polynomial Time
  Approximation Scheme (FPTAS). In FPTAS, algorithm need to polynomial
  in both the problem size n and 1/ε.


What I dont understand is the second paragraph stated above. Can someone explain to me whats the difference between FPTAS from PTAS? Can you enlighten me about exponent of the polynomial can increase dramatically as ε reduces and algorithm need to polynomial in both the problem size n and 1/ε. ? I really dont get it. Please help.
Imagine you have an $\epsilon$-approximation algorithm $A$ which runs in $n^2+2^\frac1\epsilon$ on an instance of size $n$ and another one, $B$ which runs in $n^2+\frac1\epsilon$ (to give you an other example). 

(I'm not using big-O notation to make it easier to talk about the polynomial bounds).

Now if you say $1/\epsilon$ is a constant, $2^\frac1\epsilon$ and $\frac1\epsilon$ both become constants, and you can say that the runtime of both $A$ and $B$ is bounded by a polynomial in $n$. Meaning that only $n$ is seen as a variable of that polynomial, as $\epsilon$ is a constant. So both $A$ and $B$ qualify as PTAS.

However, if this time you don't consider $1/\epsilon$ like a constant and want to include it as a variable in a polynomial upper bound, the situation changes.


For $B$, there exists some polynomial $p(x,y)$ of two variables $x$ and $y$, such that the runtime of $B$ is at most $p(n,1/\epsilon)$ for all $n,\epsilon &gt; 0$. For example, $p(x,y) = x^2 + y$ works, because $n^2+\frac1\epsilon \leq p(n,1/\epsilon)$. Thus $B$ qualifies as a FPTAS.
For $A$ however, it is not possible to find such a polynomial. For every polynomial $p(x,y)$, you know that $n^2+2^\frac1\epsilon &gt; p(n,1/\epsilon)$ once $1/\epsilon$ becomes big enough (or equivalently, once $\epsilon$ becomes small enough). Thus $A$ does not qualify as a FPTAS.