Let P be an optimization problem, and let the cost of the optimal solution be C*.

Let A be an algorithm that finds a solution to P (not necessarily the optimal solution).  Let C be the cost of the solution found by A.

If we can prove that there is a constant RHO such that

            max(C/C*, C*/C) <= RHO for all instances of P,

then we say that A is a RHO-approximation algorithm for P.

Thus the algorithm that we discussed last week is a 2-approximation algorithm for Vertex Cover.


Note that this definition is designed to make sense regardless of whether P is a "maximize" or "minimize" problem.  If the former, we know that C <= C*, so C*/C >= C/C*, and C*/C >=1.  If the latter, we know that C >= C* so C/C* >= C*/C and C/C* >= 1.  There are two observations:  The value of RHO must be >= 1, and RHO acts as an upper bound on the ratio between the optimal solution and the approximation algorithm's solution.

We started to discuss the Travelling Salesperson Problem but we didn't get very far into it.  It will  be covered in a future note document.