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

If the solution calculated by an approximation method for the input is the *quality of* the approximation method for the input

- as defined for maximization tasks and as defined for minimization tasks .

So it always is . If the algorithm delivers an optimal solution for .

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** .

## Individual evidence

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