# Differences between Polynomial and fully polynomial time approximation scheme

I have a confusion on understanding the relation between:

The input n ,The relative error and The running time of the program In both PTAS and FPTAS. In "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/ε."

My questions are: 1) How to decide if my polynomial algorithm is an approximation? Is testing all benchmarks from literature is a pre proof to continue in searching the proof?

2) How to decide the relation between the input n and the relative error, according to question 1?

• For question (1) You already know that you design an approximation algorithm for a problem and then the next step is to analyze the time complexity to see whether it runs in polynomial time or not. For (2), notice that PTAS is the class of of infinite number of algorithms, each gives you $\epsilon$-approximation algorithm for the problem. To design a PTAS, then you need to see a couple of examples, see the PTAS of Euclidean TSP or Partition problem. They are explained very well in Vazirani's textbook. Aug 12 at 15:53