Güte von Approximationsalgorithmen

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

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

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

bei Maximierungsaufgaben als und bei Minimierungsaufgaben als definiert.

Es ist also immer . Gilt , liefert der Algorithmus eine optimale Lösung für .

Hat ein Approximationsverfahren für alle möglichen Eingaben eine Güte von höchstens , so spricht man von einer -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).