# 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 ).