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 OPT(I) is the optimal cost, an approximation ratio α ≥ 1 satisfies A(I) ≤ α · OPT(I) for all instances I. For a maximization problem, the analogous bound is A(I) ≥ (1/α) · OPT(I). Additive guarantees bound the absolute difference rather than the ratio.

Guarantees can be worst-case or asymptotic; a PTAS (polynomial-time approximation scheme) provides for any ε > 0 a (1+ε)-approximation in polynomial time for all fixed ε, while an APX algorithm yields a constant-factor guarantee. Some problems have tight inapproximability results, meaning no polynomial-time algorithm can achieve better than a certain factor unless P = NP or similar assumptions.

Common examples include the 2-approximation for Vertex Cover and the 1.5-approximation for Metric Traveling Salesman Problem (via Christofides' algorithm), and the Set Cover problem with a ln n + O(1) approximation. These guarantees are used to compare algorithms and to guide the design of new methods with provable performance.

See also: approximation ratio, PTAS, APX, inapproximability.