Frage: Wie löst man ein NP-vollständiges Problem effizient?
Definition:
Ein Approximationsalgorithmus berechnet zu jeder Probleminstanz eine Lösung ,
die möglichst nah an der optimalen Lösung der Instanz liegt.
Bemerkung:
Approximationsalgorithmen mit einem konstanten absoluten Fehler sind selten.
Definition:
Die Güte eines Approximationsalgorithmus gibt an, wie nahe an der optimalen Lösung liegt:
für alle I
Klassen von Approximationsalgorithmen:
1. : in polynomialer Zeit optimal lösbar ()
2. : es existiert ein vollständig polynomiales Approximationsschema (beliebig gut)
3. : es existiert ein polynomiales Approximationsschema (exp. Laufzeit in der Güte)
4. : es exisitiert ein Approximationsalgorithmus mit Güte
(zumindest irgendwie)
5. : jeder Approximationsalgorithmus ist beliebig schlecht
Die Klassen bilden für eine echte Hierarchie, für kollabieren sie.