Approximationsfaktor

Der Approximationsfaktor, auch Approximationsverhältnis genannt, beschreibt die Qualität einer Näherungslösung zu einem Optimierungsproblem im Worst-Case. Er vergleicht den Wert der vom Algorithmus erhaltenen Lösung mit dem optimalen Wert und gibt an, wie stark die Lösung von der Optimalität abweicht.

Formell: Sei P ein Minimierungsproblem mit Instanz I und OPT(I) der optimale Wert. Ein Algorithmus A, der in polynomieller Zeit läuft, hat für alle I die Eigenschaft, value_A(I) ≤ α · OPT(I) mit α ≥ 1. Dann ist A ein α-Approximationsalgorithmus. Für Maximierungsprobleme gilt analog: value_A(I) ≥ (1/α) · OPT(I) oder, äquivalent, OPT(I) ≤ α · value_A(I). In beiden Fällen bezeichnet α den Approximationsfaktor oder das Approximationsverhältnis. Kleinere Faktoren bedeuten bessere Näherung; häufige Bezeichnungen sind 2-Approximation, (1+ε)-Approximation oder ln n-Approximation.

Beispiele: Für das Vertex-Cover-Problem liefert ein naiver Greedy-Algorithmus eine 2-Approximation. Das Set-Cover-Problem besitzt eine ln n-Approximation, und es existieren PTAS- bzw. FPTAS-Resultate für bestimmte spezielle Probleme.

Beziehung zu anderen Konzepten: Der Approximationsfaktor ist eng mit PTAS (Polynomialzeit-Approximationsschema) und FPTAS (Fully Polynomial-Time Approximation Scheme) verbunden. Ein PTAS bedeutet, dass für jedes ε > 0 eine in Zeit poly(n,1/ε) laufende (1+ε)-Approximation existiert. Eine FPTAS erhöht diese Eigenschaft weiter zu einer Laufzeit, die zusätzlich polynomial in 1/ε ist. In vielen Fällen handelt es sich um NP-schwere Probleme, weshalb exakte Polynomialzeit-Lösungen nicht bekannt oder unwahrscheinlich sind.