Güte von Approximationsalgorithmen

Die Güte v​on Approximationsalgorithmen d​ient zur Bewertung d​er approximativen Lösung.[1]

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

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

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

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

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

Einzelnachweise

1. Walz, Guido,: Lexikon der Mathematik. Spektrum, Akad. Verl, Heidelberg, ISBN 3-8274-0433-9 (spektrum.de).