I am trying to understand how we can 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's 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.
I don't think you understand what PTAS means. You don't "apply it on an algorithm", and you don't "insert" any terms in its running time. You have a minimization problem for which there may or may not be an efficient algorithm. But what you do have is an algorithm that, given any instance $x$ of the problem and a rational number $r > 1$, produces a solution whose objective value is at most $r$ times the optimal value. For any given $r$ the running time of this algorithm is polynomial in the size of $x$ (but the dependence on $r$ is arbitrary, so it may be extremely hard to get very good approximations). That is a Polynomial-Time Approximation Scheme or PTAS for your problem.