I am trying to understand what is the PTAS, FPTAS and what is the difference between them.

I found this analysis:

PTAS definition vs. FPTAS

but I cannot understand what do we mean by saying:

"....time complexity is polynomial in the input size and also polynomial in 1/ϵ" ?? Ok n has to do with the linear O(n) worst case that the algorithm runs. But O(1/ε) how does it work?


For example, the running time $O(2^{1/\varepsilon} \cdot n^2)$ corresponds to a PTAS, since the running time depends polynomialy on $n$, but not on $1/\varepsilon$ since it is in the exponent. The running time $O(1/\varepsilon \cdot n \log{n})$ depends polynomialy on $n$ and $1/\varepsilon$, so it corresponds to a FPTAS.

NB, you also need to show that your algorithm has an approximation ratio of $(1 + \varepsilon)$ (or -) to show the algorithm is in fact a (F)PTAS.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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