Approximation ratio

The approximation ratio for a given approximation algorithm $M$ on input $w$ is the real value $R_M(w)\ge 1$ such that:

$$\begin{array}{rl}{R}_M(w)& =max\left(\begin{array}{c}\frac{C_{\text{approx}}}{C_{\text{global}}},\frac{C_{\text{global}}}{C_{\text{approx}}}\end{array}\right)\\ & =\{\begin{array}{ll}\frac{C_{\text{approx}}}{C_{\text{global}}}& \text{if }{C}_{\text{global}}\le C_{\text{approx}}\\ \frac{C_{\text{global}}}{C_{\text{approx}}}& \text{if }{C}_{\text{global}}>C_{\text{approx}}\end{array}\end{array}$$

• Where $C_{\text{approx}}$ is the cost of the approximate solution.
• Where $C_{\text{global}}$ is the cost of the optimal solution.