Güte von Approximationsalgorithmen

Die Güte von Approximationsalgorithmen dient zur Bewertung der approximativen Lösung.^[1]

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.

Einzelnachweise

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

Basierend auf einem Artikel in:

Wikipedia.de