Quality of approximation algorithms

from Wikipedia, the free encyclopedia

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

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