0
$\begingroup$

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?

Improve this question
$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – user777
    Aug 12, 2021 at 15:53

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ @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. $\endgroup$
    – D.W. ♦
    Aug 11, 2021 at 20:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.