Güte von Approximationsalgorithmen

Die Güte von Approximationsalgorithmen dient zur Bewertung der approximativen Lösung.

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 die 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. Die garantierte Güte eines Algorithmus ist die Gütegarantie.