Differences between Polynomial and fully polynomial time approximation scheme

Question

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?

• user777: 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.

Answer 1

You can't verify an algorithm is a FPTAS using benchmarks. To be a FPTAS, the algorithm must provide a good approximation for all possible inputs. There are infinitely many input sizes. Observing whether it works on finitely many inputs can never tell you whether it works on all possible inputs.

Instead, you must come up with a mathematical proof that it is a FPTAS.

• D.W.: @SAbeA, I already answered your question in the last sentence of my answer. I suggest spending more time studying the subject, reading textbooks, and reading some examples of FPTAS algorithms and how they prove that it is a FPTAS.