Giving an algorithm A for problem P, where the running time of A is polynomial in the description of the instance I of problem P, we denote by A(I) the value of the solution given by A on a generic instance I and by OPT(I) the value of the optimal solution for instance I. We say that the algorithm A is r approximated if for any possible instance of the problem, the solution given by A is at most r times the optimal solution for instance I. This is for minimisation problem. On the other hand, if we deal with a maximisation problem, our algorithm is said to be r approximated if for every instance I of the maximisation problem we get a benefit that is at least a fraction r of the optimal solution.

---