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.