Approximationsalgorithmus

Ein Approximationsalgorithmus ist ein Algorithmus, der für ein Optimierungsproblem eine Lösung liefert, die möglichst nahe an einer optimalen Lösung ist. Die Güte eines Approximationsalgorithmus ist das Verhältnis von approximierter Lösung zu optimaler Lösung. Wenn ein Algorithmus immer eine optimale Lösung liefert, ist seine Güte 1, ansonsten größer. Im allgemeinen versteht man unter Approximationsgüte die absolute Approximationsgüte, das ist die Güte, die ein Algorithmus bei beliebiger Eingabe nicht überschreitet. Die asymptotische Approximationsgüte ist der Grenzwert der Approximationsgüte wenn das Optimum der Lösung gegen Unendlich geht.

Neben Algorithmen mit einem konstanten Approximationswert (Algorithmen, die immer um einen - möglicherweise gebrochenen - Wert schlechter sind als das Optimum), gibt es auch sogenannte Approximationsschemata, die es ermöglichen eine beliebig genaue Annäherung an das Optimum zu berechnen, wobei die Laufzeit polynomiell in der Eingabelänge bleibt. Hierbei gibt es folgende verschiedene Varianten:

FPAS

Der Algorithmus berechnet eine (1+ε)-Approximation, deren Laufzeit polynomiell in der Länge der Eingabe und 1/ε beschränkt ist.

PAS

Wie FPAS, nur ist hier die Laufzeit nur polynomiell in der Länge der Eingabe beschränkt.

Super-PAS

Wie FPAS, nur ist hier die Laufzeit polynomiell in der Länge der Eingabe und in der Länge von ε (also in log(1/ε)) beschränkt.