approximationsgaranti
Approximationsgaranti, or approximation guarantee, is a formal bound used to evaluate the quality of solutions produced by approximation algorithms for optimization problems. It expresses how close the algorithm's output is to the best possible solution, the optimum, under worst-case inputs.
For a minimization problem, if algorithm A returns a solution with cost A(I) for instance I and
Guarantees can be worst-case or asymptotic; a PTAS (polynomial-time approximation scheme) provides for any ε > 0 a
Common examples include the 2-approximation for Vertex Cover and the 1.5-approximation for Metric Traveling Salesman Problem
See also: approximation ratio, PTAS, APX, inapproximability.