I am trying to apply PTAS on an algorithm. I think that we apply PTAS on the running time equation of the algorithm. We use the term (1-ϵ) and (1+ ϵ) in the running time of the algorithm but I don’t know how we insert these terms in the running time equation of the algorithm, and that’s what I want to understand. Also how we evaluate the value of ϵ.

Let suppose we have a algorithm:

M = K * Y Let’s the running time of algorithm is pseudo-polynomial i.e p(n) * K where k and p(n) are polynomial in n. Somebody please guide me.


  • $\begingroup$ you can use $\epsilon$ for any constant. For example, if you choose $\epsilon=0.01$, then the running time would be: $O(n^{1/\epsilon} ) = O(n^{100} )$. The more $\epsilon$ comes close to zero, the more close to its optimal value, but it takes a lot of time to produce the result. This is the idea of PTAS (en.wikipedia.org/wiki/Polynomial-time_approximation_scheme) $\endgroup$ – user777 May 31 at 8:54
  • $\begingroup$ another point, note that ($\epsilon +1) is for minimization and ($\epsilon -1) for minimization. The reason is that maximization problem has ratio between (0-1] and minimization problem has ratio between $[1-\infty)$. $\endgroup$ – user777 May 31 at 8:58
  • $\begingroup$ please look at Vaziran's textbook for basic definitions or CLRS in chapter about approximation algorithm for definition of ratios. For definition of PTAS, FPTAS see complexity zoo definition. $\endgroup$ – user777 May 31 at 9:00
  • $\begingroup$ you bring the issue of pseudo-polynomial time. It is known that if NP-hard problem is weakly, then it admits a FPTAS, see knapsack problem. Weakly NP-hard problem is called sometimes a number problem. If O(Km) is the running time of weakly NP-hard problem, then if m is the number of items or size of inputs in bits, then K is a constant but not bounded by poly(m). I hope I clarify something here. $\endgroup$ – user777 May 31 at 9:51

Your Answer

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

Browse other questions tagged or ask your own question.