# Applying Polynomial Time Approximation Scheme (PTAS) on an Algorithm

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.

Zulfi.

• 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) – user777 May 31 at 8:54
• 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)$. – user777 May 31 at 8:58
• 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. – user777 May 31 at 9:00
• 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. – user777 May 31 at 9:51