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.