Editing Approximation algorithm (section)

== Performance guarantees ==
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.

:<math>\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}</math>

The factor ''ρ'' is called the ''relative performance guarantee''. An approximation algorithm has an ''absolute performance guarantee'' or ''bounded error'' ''c'', if it has been proven for every instance ''x'' that

:<math> (\mathrm{OPT} - c) \leq f(x) \leq (\mathrm{OPT} + c).</math>

Similarly, the ''performance guarantee'', ''R''(''x,y''), of a solution ''y'' to an instance ''x'' is defined as

:<math>R(x,y) =  \max \left ( \frac{OPT}{f(y)}, \frac{f(y)}{OPT} \right ),</math>

where ''f''(''y'') is the value/cost of the solution ''y'' for the instance ''x''. Clearly, the performance guarantee is greater than or equal to 1 and equal to 1 if and only if ''y'' is an optimal solution. If an algorithm ''A'' guarantees to return solutions with a performance guarantee of at most ''r''(''n''), then ''A'' is said to be an ''r''(''n'')-approximation algorithm and has an ''approximation ratio'' of ''r''(''n''). Likewise, a problem with an ''r''(''n'')-approximation algorithm is said to be r''(''n'')''-''approximable'' or have an approximation ratio of ''r''(''n'').<ref name=ausiello99complexity>{{cite book|title=Complexity and Approximation: Combinatorial Optimization Problems and their Approximability Properties|year=1999|author1=G. Ausiello |author2=P. Crescenzi |author3=G. Gambosi |author4=V. Kann |author5=A. Marchetti-Spaccamela |author6=M. Protasi }}</ref><ref name="kann92onthe">{{cite book|title=On the Approximability of NP-complete Optimization Problems|author=Viggo Kann|year=1992|url=https://www.csc.kth.se/~viggo/papers/phdthesis.pdf}}</ref>

For minimization problems, the two different guarantees provide the same result and that for maximization problems, a relative performance guarantee of ρ is equivalent to a performance guarantee of <math>r = \rho^{-1}</math>. In the literature, both definitions are common but it is clear which definition is used since, for maximization problems, as ρ ≤ 1 while r ≥ 1.

The ''absolute performance guarantee'' <math>\Rho_A</math> of some approximation algorithm ''A'', where ''x'' refers to an instance of a problem, and where <math>R_A(x)</math> is the performance guarantee of ''A'' on ''x'' (i.e. ρ for problem instance ''x'') is:

:<math> \Rho_A = \inf \{ r \geq 1 \mid R_A(x) \leq r, \forall x \}.</math>

That is to say that <math>\Rho_A</math> is the largest bound on the approximation ratio, ''r'', that one sees over all possible instances of the problem. Likewise, the ''asymptotic performance ratio'' <math>R_A^\infty</math> is:

:<math> R_A^\infty = \inf \{ r \geq 1 \mid \exists n \in \mathbb{Z}^+, R_A(x) \leq r, \forall x, |x| \geq n\}. </math>

That is to say that it is the same as the ''absolute performance ratio'', with a lower bound ''n'' on the size of problem instances. These two types of ratios are used because there exist algorithms where the difference between these two is significant.

{| class="wikitable"
|+Performance guarantees
|-
!  !! ''r''-approx<ref name="ausiello99complexity"/><ref name="kann92onthe"/> !! ''ρ''-approx !! rel. error<ref name="kann92onthe"/> !! rel. error<ref name="ausiello99complexity"/> !! norm. rel. error<ref name="ausiello99complexity"/><ref name="kann92onthe"/> !! abs. error<ref name="ausiello99complexity"/><ref name="kann92onthe"/>
|-
! max: <math>f(x) \geq</math>
| <math>r^{-1} \mathrm{OPT}</math> || <math>\rho \mathrm{OPT}</math> || <math>(1-c)\mathrm{OPT}</math> || <math>(1-c)\mathrm{OPT}</math> || <math>(1-c)\mathrm{OPT} + c\mathrm{WORST}</math> || <math>\mathrm{OPT} - c</math>
|-
! min: <math>f(x) \leq</math>
| <math>r \mathrm{OPT}</math> || <math>\rho \mathrm{OPT}</math> || <math>(1+c)\mathrm{OPT}</math> || <math>(1-c)^{-1}\mathrm{OPT}</math> || <math>(1-c)^{-1} \mathrm{OPT} + c\mathrm{WORST}</math> || <math>\mathrm{OPT} + c</math>
|-
|}