Ein Approximationsalgorithmus ist in der Informatik ein Algorithmus der ein Optimierungsproblem näherungsweise löst.

Viele Optimierungsprobleme lassen sich mit exakten Algorithmen nicht effizient lösen. Für solche Probleme kann ist es sinnvoll sein, wenigstens eine Lösung zu finden, die einer optimalen Lösung möglichst nahe kommen.

Güte von Approximationsalgorithmen

---

Für jede mögliche Eingabe $x$ gebe es einen Lösungsraum $S(x)$, und zu jeder möglichen Lösung $y\; \backslash in\; S(x)$ eine Güte $v(x)\; \backslash leq\; k$, die optimale Lösung heißt $v^*$. Ein Approximationsalgorithmus sucht nun nach einer Lösung $y\; \backslash in\; S(x)$, so dass $v(y)$ möglichst nah an $v^*$ liegt.

Die Güte eines Approximationsverfahrens wird durch die Performanz $r$, die auch Approximationsgüte genannt wird, des Algorithmus bestimmt. Sie ist definiert durch das Verhältnis von approximierter Lösung zur exakten Lösung, gemessen in einer angemessenen Norm. Die Performanz einer Lösung $y\backslash in\; S(x)$ wird bestimmt durch:

$r\; =\; min\; \backslash \{\backslash frac\{v(y)\}\{v^*\},\backslash frac\{v^*\}\{v(y)\}\backslash rbrace$

Diese Definition der Performanz kann sowohl auf Minimierungs- wie auch auf Maximierungsprobleme angewandt werden. Es gilt immer $r\; \backslash leq\; 1$.

Klassen von Approximationsalgorithmen

---

Optimierungsprobleme werden in der theoretischen Informatik in verschiedene Approximationsklassen unterschieden, je nachdem welcher Grad an Approximation möglich ist:

APX:

Die Abkürzung APX steht für approximable und deutet an, dass das Optimierungsproblem, zumindest bis zu einem gewissen Grad, effektiv approxmierbar ist.

Ein Problem liegt in der Klasse APX, wenn eine Zahl $\backslash delta\; \backslash in\; (0,1)$ und ein polynomialer Algorithmus existiert, der bei jeder zulässigen Eingabe $x$ eine Lösung mit einer Performanz $r\; \backslash geq\; 1-\backslash delta$ liefert.

PTAS/PAS:

PTAS oder PAS steht für polynimial time approximation scheme. Anders als bei der Klasse APX wird hier für jedes $\backslash delta\; \backslash in\; (0,1)$ gefordert, dass ein polynomialer Algorithmus existiert, der bei jeder zulässigen Eingabe eine Lösung mit einer Performanz $r\; \backslash geq\; 1-\backslash delta$ liefert. Der Algorithmus muss also nicht nur für eine bestimmte Performanz, sondern für jede Performanz effektiv sein, der Existenzqauntor wird durch einen Allquantor ersetzt.

FPTAS:

FPAS steht für fully polynimial time approximation scheme. Hier wird gefordert, das sich der Algorithmus nicht nur polynomial zur Eingabe sondern auch zur Güte der Approximation verhält. Das es also zu jeder Eingabe $x$ und jedem $k\; \backslash in\; \backslash mathbb\{N\}$ eine Lösung mit der Performanz $r\; \backslash geq\; 1-1/k$ gibt, wobei der Algorithmus polynomial in $x$ und $k$ ist.

Es gilt: $FPTAS\; \backslash subseteq\; PTAS\; \backslash subseteq\; APX$

Unter der Annahme $P\; \backslash neq\; NP$ sind die obigen Inklusionsabbildungen echte Inklusionen. Das heißt es gibt zum Beispiel mindestens ein Optimierungsproblem, das in der Klasse PTAS liegt, aber nicht in der Klasse FPTAS.

Fasst man die Inklusionskette etwas weiter:
{Optimierungsprobleme in P}$\backslash subseteq\; FPTAS\; \backslash subseteq\; PTAS\; \backslash subseteq\; APX\; \backslash subseteq${Optimierungsprobleme in NP}

hieße das auch, dass es Optimierungsprobleme gibt, die nicht einmal in APX liegen. Dies lässt sich unter der Annahme das $P\; \backslash neq\; NP$ zum Beispiel für das Cliquenproblem zeigen.

Siehe auch: Heuristik

Theoretische_Informatik