What?

Take an NP Hard problem. In Greedy Approximation Algorithms, we saw the definition for a close to optimal solution. But how do we know if our solution is close to the close to the optimal solution? The approximation ratio.

Formula (For minimisation problems):

Formula (For maximisation problems):

What’s a good ratio?

Well the closer to 1 it is, the better. If (for minimisation), then the approximate solution is twice as costly as the optimal solution.