Quality of approximation algorithms

The quality of an approximation algorithm is used to evaluate the approximate solution .

Let it be the set of feasible solutions belonging to an input . For every possible solution, let the value of the objective function for . Let the objective function value of an optimal solution for the input be . An approximation algorithm (or approximation method) outputs a solution on input so that is relatively close to . ${\displaystyle S(I)}$ ${\displaystyle I}$ ${\displaystyle y\in S(I)}$ ${\displaystyle v(y)}$ ${\displaystyle y}$ ${\displaystyle I}$ ${\displaystyle v^{*}}$ ${\displaystyle I}$ ${\displaystyle y\in S(I)}$ ${\displaystyle v(y)}$ ${\displaystyle v^{*}}$

If the solution calculated by an approximation method for the input is the quality of the approximation method for the input ${\displaystyle y}$ ${\displaystyle I}$ ${\displaystyle I}$

as defined for maximization tasks and as defined for minimization tasks . ${\displaystyle r_{I}={\frac {v^{*}}{v(y)}}}$ ${\displaystyle r_{I}={\frac {v(y)}{v^{*}}}}$

So it always is . If the algorithm delivers an optimal solution for . ${\displaystyle r_{I}\geq 1}$ ${\displaystyle r_{I}=1}$ ${\displaystyle I}$

If an approximation method has a quality of at most for all possible inputs , then one speaks of an approximation . The guaranteed quality of an algorithm is the quality guarantee . ${\displaystyle I}$ ${\displaystyle r_{I}}$ ${\displaystyle \alpha }$ ${\displaystyle \alpha }$

Individual evidence

1. ^ Walz, Guido: Lexikon der Mathematik . Spektrum, Akad. Verl, Heidelberg, ISBN 3-8274-0433-9 ( Spektrum.de ).