Approximationsschemata
Teubner eBooks · 2007
In den beiden vorhergehenden Kapiteln haben wir Approximationsalgorithmen kennengelernt, deren Abweichung von der optimalen Lösung fest ist. Wir wissen bei diesen Algorithmen nicht, wie man eine noch bessere Lösung errechnen kann außer dadurch, das Problem exakt mit einem Algorithmus exponentieller Laufzeit zu lösen. Aber könnte man nicht — in Anlehnung an einen Begriff wie „Konvergenz“ aus der Mathematik — die Genauigkeit einer Lösung durch Anwachsenlassen der Laufzeit „erkaufen“? D. h. es soll möglich sein, den relativen Fehler als zusätzliche Eingabe dem Algorithmus mitzugeben, so daß die Ausgabe höchstens um diesen Fehler von der optimalen Lösung abweicht. Die Laufzeit darf von diesem Fehler abhängen. Mit anderen Worten: Wir wünschen uns, daß der relative Fehler immer näher an 0 kommt, je mehr Laufzeit dem Algorithmus erlaubt ist. Allerdings sollen sich der relative Fehler und die Erhöhung der Laufzeit „gutartig“ zueinander verhalten. Diese Überlegung führt zum Begriff des Approximationsschemas. Wir stellen in diesem Kapitel ein solches Approximationsschema für Rucksack vor und beschließen es damit zu beweisen, daß es zu den Optimierungsproblemen mit sog. stark NP-vollständigen Entscheidungsvarianten vermutlich keine Approximationsschemata gibt.