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