Introduction to Computation Theory
Lead instructor: Josh Grochow
7.3 Approximation algorithms » Quiz Explanation
1) In order for an algorithm to guarantee that its output is within a factor of 3 of the optimum value, it must know the optimum value first.
False - The 2-approximation algorithm for vertex cover shown in the video doesn't need to know what the true optimum is, and nonetheless it can guarantee to get within a factor of 2 of that optimum. This is essentially the case for all approximation algorithms for NP-hard problems.
2) Assuming , is it the case that (a) some, (b) all, or (c) no -complete problems have polynomial-time c-approximation algorithms for some constant c?
A - We saw a 2-approximation algorithm for Minimum Vertex Cover, which is NP-complete. Max-Clique, however, does not have a c-approximation algorithm unless P=NP.
3) There exists a problem in and a constant c such that c - approximating this problem in polynomial time implies .
True - We mentioned that Dinur \& Safra (2005) showed that if Minimum Vertex Cover could be approximated to within a factor better than $1.3606...$ in polynomial time, then .
4) The approximation ratio of an algorithm is a good indicator of how it will perform in practice.
Sometimes - Sometimes it is. But as we saw from David Johnson's example, sometimes the worst-case approximation ratio can be misleading when the instances you are testing it on are not the worst-case.