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
Beispiele: Für das Vertex-Cover-Problem liefert ein naiver Greedy-Algorithmus eine 2-Approximation. Das Set-Cover-Problem besitzt eine ln n-Approximation,
Beziehung zu anderen Konzepten: Der Approximationsfaktor ist eng mit PTAS (Polynomialzeit-Approximationsschema) und FPTAS (Fully Polynomial-Time Approximation