# Do Approximation Algorithms Analyzed in the Worst Case?

From wikipedia:

For some approximation algorithms it is possible to prove certain properties about the approximation of the optimum result. For example, a $$ρ$$-approximation algorithm $$A$$ is defined to be an algorithm for which it has been proven that the value/cost, $$f(x)$$, of the approximate solution $$A(x)$$ to an instance $$x$$ will not be more (or less, depending on the situation) than a factor $$ρ$$ times the value, OPT, of an optimum solution.

$$\begin{cases}\mathrm{OPT} \leq f(x) \leq \rho \mathrm{OPT},\qquad\mbox{if } \rho > 1; \\ \rho \mathrm{OPT} \leq f(x) \leq \mathrm{OPT},\qquad\mbox{if } \rho < 1.\end{cases}$$

For a maximization problem, a $$\rho$$-approximation algorithm means that, for an instance $$x$$, $$\rho \mathrm{OPT} \leq f(x) \leq \mathrm{OPT}$$, for any $$\rho<1$$. Is this mean that in the worst case the algorithm produces a solution that is at least $$\rho \mathrm{OPT}$$? Or is this in the average case? Because there are some instances where the algorithm find the optimal solution.

I mean, if the algorithm is executed, say $$10000$$ times (with randomly generated instances) and produces $$\mathrm{OPT}$$, say $$9995$$ times and $$5$$ times it produces a value that is greater than $$\rho\mathrm{OPT}$$. What can we say about the algorithm then?

It's a worst case guarantee. It can in some cases do better than $\rho OPT$, but it will never do worse.
It is the worst case. $\rho$ can be one sided bound as in examples you provided or bounded on both sides (example is in next paragraph on wikipedia).
This might be the case $$\mathrm(OPT - c) \leq f(x) \leq \mathrm(OPT + c)$$ But still it might be bounded on one side but situation you have is due to roundoff problems of floating point values.
• Please edit your answer to use the same notation as in the question, which calls the approximation factor $\rho$ (rho). Also, you can use LaTeX for mathematics. Jul 30, 2015 at 19:28