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?