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\ge 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.