Güte von Approximationsalgorithmen

Die Güte v​on Approximationsalgorithmen d​ient zur Bewertung d​er 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).
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. The authors of the article are listed here. Additional terms may apply for the media files, click on images to show image meta data.