Approximation Ratio

Measure for how close the suboptimal solution from an Approximation Algorithm is to the optimal solution.

Formally, we say that an algorithm for a problems has an approximation ratio of $\rho (n)$ if, for any input of size $n$, the cost $C$ of the solution produced by the algorithm is within a factor of $\rho (n)$ of the cost $C\text{*}$ of an optimal solution: \max \left( \frac{C}{C^{}^{}^\*}, \frac{C^\*}{C} \right) \leq \rho(n)

If an algorithm achieves an approximation ratio of $\rho (n)$, it is called a ρ(n)-approximation algorithm.

The approximation ratio is never less than 1, since $C/C^{\text{*}}\le 1$ implies $C^{\text{*}}/C\ge 1$. Therefore a 1-approximation algorithm produces an optimal solution and an algorithm with a larger ratio returns a solution worse than optimal.

The ratio works for both maximization and minimization problems:

• Maximization: We by definition that $0<C\le C^{\text{*}}$ and therefore the ratio $C^{\text{*}}/C$ will dominate the max function and represent $\rho (n)$
• Minimization: We have by definition that $0<C^{\text{*}}\le C$ and therefore the ratio $C/C^{}\text{*}$ will dominate the max function and represent $\rho (n)$.

If an algorithm is a randomized approximation algorithm then the expected cost plays the role of C.