Applying Polynomial Time Approximation Scheme (PTAS) on an algorithm

[zak100]

Hi,

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.