Viele Fragestellung aus der Praxis sind nicht direkt Entscheidungsprobleme, wie sie in der klassischen Komplexitätstheorie meist betrachtet werden, sondern es stellt sich vielmehr die Frage nach der Berechnung einer besten aus einer Menge vieler Lösungen. Auch wenn das Auffinden einer besten Lösung meist schwierig ist, so lassen sich für viele Probleme zumindest gute Lösungen effizient berechnen mit Hilfe sogenannter Approximationsalgorithmen. Dabei wird eine Garantie für die Qualität der berechneten Lösung in Form einer beweisbaren Güte, einer Art maximaler Abweichung von der besten Lösung, angegeben. In dieser Vorlesung werden grundlegende Konzepte und gängige Techniken vorgestellt, um einerseits Approximationsalgorithmen zu entwickeln und andererseits Grenzen dieser algorithmischen Lösungsmethodik zu untersuchen.
