Approximationsalgorithmus

Ein Approximationsalgorithmus ist ein Algorithmus, der für ein mathematisches Problem eine Näherungslösung liefert, die möglichst nahe an der exakten Lösung ist.

Die Güte eines Approximationsalgorithmus ist das Verhältnis von approximierter Lösung zur exakten Lösung, gemessen in einer angemessenen Norm. Wenn ein Algorithmus immer die exakte Lösung liefert, ist seine Güte 1, ansonsten größer. Im allgemeinen versteht man unter Approximationsgüte

Neben Algorithmen mit einem konstanten Approximationswert (Algorithmen, die immer um einen - möglicherweise gebrochenen - Wert schlechter sind als das Optimum), gibt es auch so genannte Approximationsschemata, die es ermöglichen, eine beliebig genaue Annäherung der Lösung zu berechnen, wobei die Laufzeit polynomiell in der Anzahl der Eingabevariablen bleibt. In der theoretischen Informatik unterscheidet man folgende verschiedene Varianten:

FPAS (manchmal auch FPTAS - fully polynomial time approximation scheme)

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

PAS (auch PTAS)

Wie FPAS, nur ist hier die Laufzeit nur polynomiell in der Länge der Eingabe beschränkt. Der Unterschied zum FPAS besteht darin, dass die Laufzeit von PAS-Algorithmen 1/ε im Exponenten enthalten darf. Da ε in der Regel ein sehr kleiner Wert ist, ist 1/ε groß, und die Laufzeit hängt exponentiell von der Approximationsgüte ab!

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.