Approximationsalgorithmus

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

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

Güte von Approximationsalgorithmen

Es sei $S(I)$ die zu einer Eingabe $I$ gehörige Menge zulässiger Lösungen. Zu jeder möglichen Lösung $y\in S(I)$ sei $v(y)$ der Wert der Zielfunktion für $y$. Der Zielfunktionswert einer optimalen Lösung für Eingabe $I$ sei $v^{*}$. Ein Approximationsalgorithmus (oder Approximationsverfahren) gibt bei Eingabe $I$ eine Lösung $y\in S(I)$ aus, so dass $v(y)$ relativ nah an $v^{*}$ liegt.

Ist $y$ die von einem Approximationsverfahren für die Eingabe $I$ berechnete Lösung, so ist die Güte des Approximationsverfahrens bei der Eingabe $I$

bei Maximierungsaufgaben als $r_{I}={\frac {v^{*}}{v(y)}}$ und bei Minimierungsaufgaben als $r_{I}={\frac {v(y)}{v^{*}}}$ definiert.

Es ist also immer $r_{I}\geq 1$. Gilt $r_{I}=1$, liefert der Algorithmus eine optimale Lösung für $I$.

Hat ein Approximationsverfahren für alle möglichen Eingaben $I$ eine Güte $r_{I}$ von höchstens $\alpha$, so spricht man von einer $\alpha$-Approximation.

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, effizient approximierbar ist. Ein Problem liegt in der Klasse APX, wenn eine Zahl $r$ und ein polynomieller Algorithmus, der bei jeder zulässigen Eingabe $I$ eine Lösung mit einer Güte $\leq r$ liefert, existieren.

PTAS/PAS

PTAS oder PAS steht für polynomial time approximation scheme. Anders als bei der Klasse APX wird hier für jedes $\delta \in (0,1)$ gefordert, dass ein polynomialer Algorithmus existiert, der bei jeder zulässigen Eingabe eine Lösung mit einer Güte $r\leq 1+\delta$ liefert. Der Algorithmus muss also nicht nur für eine bestimmte Güte, sondern für jede Approximationsgüte effizient sein.

FPTAS

FPTAS steht für fully polynomial time approximation scheme. Hier wird gefordert, dass sich der Algorithmus nicht nur polynomiell zur Eingabe, sondern auch zur Güte der Approximation verhält; Dass er also zu jeder Eingabe $I$ und jedem $k\in \mathbb {N}$ eine Lösung mit der Güte $r\leq 1+1/k$ ausgibt und seine Laufzeit polynomiell in $x$ und $k$ ist.

Es gilt: $PO\subseteq FPTAS\subseteq PTAS\subseteq APX\subseteq NPO$

Unter der Annahme $P\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. Unter dieser Annahme existiert auch mindestens ein Optimierungsproblem, das nicht in APX liegt. Dies lässt sich unter der Annahme $P\subsetneq NP$ zum Beispiel für das Cliquenproblem zeigen.

Sei $\Pi$ ein Optimierungsproblem, dessen Zielfunktion $v\colon S(I)\to \mathbb {N}$ für alle Instanzen $I$ ganzzahlig ist. Falls es ein Polynom $p$ mit $opt(I)<p(|I|,maxnr(I))$ für jede Instanz $I$ gibt, dann folgt aus der Existenz eines FPTAS für $\Pi$ die Existenz eines pseudopolynomiellen Algorithmus für $\Pi$. Hierbei ist $opt(I)$ die optimale Lösung für die Instanz $I$ und $maxnr(I)$ der maximale Wert einer Variable von $I$.

Da stark NP-vollständige Probleme keinen pseudopolynomiellen Algorithmus haben (falls $P\neq NP$), besitzen diese daher kein FPTAS.

Siehe auch

• Heuristik

Literatur

• Rolf Wanka: Approximationsalgorithmen – Eine Einführung, Teubner, Wiesbaden, 2006, ISBN 3-519-00444-5
• Klaus Jansen, Marian Margraf: Approximative Algorithmen und Nichtapproximierbarkeit, de Gruyter, Berlin, New York, 2008, ISBN 978-3-11-020316-5