Complexity Explorer Santa Fe Institute

Introduction to Computation Theory

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.