Complexity Explorer Santa Few Institute

Introduction to Computation Theory

Enroll

Lead instructor:

Your progress is not being saved! Enroll now or log in to track your progress or submit homework.

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 $\mathsf{P} \neq \mathsf{NP}$, is it the case that (a) some, (b) all, or (c) no $\mathsf{NP}$-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 $\mathsf{NP}$ and a constant c such that c - approximating this problem in polynomial time implies $\mathsf{P}=\mathsf{NP}$.

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 $\mathsf{P}=\mathsf{NP}$.

 

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.