Understanding Polynomial TIme Approximation Scheme

Question

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.

Answer 1

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!

Answer 2

Vertex cover having 2-approximation algorithm is not same as having a PTAS algorithm. Sometimes, there are problems where much better approximation is possible. These problems then admit PTAS.

Such algorithms take an instance of the problem as input, with another input parameter epsilon>0. And it gives an output whose value is at most (1+epsilon).OPT for minimisation problem; and (1/(1+epsilon)).OPT for maximisation problem.

Run time of a PTAS algorithm is polynomial in n (size of problem instance). Sometimes, the runtime is also polynomial in epsilon, then its called to admit FPTAS(fully PTAS).

Example: Dynamic programming algorithm for KNAPSACK with integer-profits gives optimal solution. While, KNAPSACK problem with real-valued profits do not admit polynomial-time algorithm. But it admits a FPTAS, where real-value profits are converted into integer profits; and DP algorithm is used to calculate the solution with "rounded" profits.

Another example, Max Independent Set does not admit a PTAS or FPTAS. Because, in this case, we can set a value for epsilon, which will always give optimal solution for any graph using that PTAS algorithm; which is not possible until P=NP.