Is an approximation algorithm the same as a Polynomial Time Approximation Algorithm (PTAS)? E.g. It can be shown that A(I) <= 2 * OPT(I) for vertex cover. Does it mean that Vertex Cover has a 2-polynomial time approximation algorithm or a PTAS?
Thanks!
Note: The text in Italics is the edit I made after I posted my question.
No, this isn't necessarily the case. A PTAS is an algorithm where given any ε > 0, you can approximate the answer to a factor of (1 + ε) in polynomial time. In other words, you can get arbitrarily good approximations.
Some problems are known (for example, MAX-3SAT) that have approximation algorithms for specific factors (for example, 5/8), but where it's known that unless P = NP there is a hard limit to how well the problem can be approximated in polynomial time. For example, the PCP theorem says that MAX-3SAT doesn't have a polynomial-time 7/8 approximation unless P = NP. It's therefore possible that MAX-3SAT has a PTAS, but only if P = NP.
Hope this helps!