Viele Optimierungsprobleme, die in praktischen Anwendungen sehr oft vorkommen, sind NP-schwer. Wenn nun angenommen wird, dass die Problemklassen P und NP nicht gleich sind, dann ist die Lösung dieser Probleme aus praktischer Sicht nicht möglich - sie würde sehr viele Ressourcen (Zeit und evtl. Speicherplatz) in Anspruch nehmen.
Ein möglicher Ausweg aus diesem Dilemma bildet der Einsatz von Approximationsalgorithmen. Hierbei versucht man das gegebene Optimierungsproblem nicht mehr exakt zu lösen (da dieses ja höchstwahrscheinlich nicht in Polynomzeit möglich ist), sondern man versucht die optimale Lösung bestmöglich in Polynomzeit zu approximieren.
Im Rahmen dieses Seminars wird zunächst eine Einführung in das Gebiet der Approximationsalgorithmen erfolgen, und es werden allgemeine Approximationstechniken eingeführt. Darauf aufbauend werden dann Approximationsalgorithmen für verschiedene Probleme betrachtet. Der Schwerpunkt wird hierbei auf Graphproblemen liegen.
The seminar talks can be presented in German or English, depending on the preference of the students.