Gegenstand der Vorlesung
Für sehr viele wichtige Optimierungsprobleme sind
keine Polynomialzeitalgorithmen bekannt, die das Problem exakt lösen.
Dann bieten sich Algorithmen an, die zwar nicht das Optimum finden,
aber Lösungen, die dicht am Optimum liegen, so genannte
Approximationsalgorithmen. Um diese geht es in dieser Vorlesung, die,
wie auch die entsprechende Literatur, problemorientiert ist, das heißt,
pro "Kapitel" wird jeweils ein bestimmtes Problem behandelt und
einige für das Problem existierende Approximationsalgorithmen vorgestellt.
Vorkenntnisse aus der Vorlesung "Effiziente Algorithmen" sind hilfreich,
aber nicht notwendig.
Grundlage der Vorlesung sind (u.a.) die Bücher "Approximation Algorithms"
von V.V. Vazirani und "Approximation Algorithms for NP-hard Problems"
von D.S. Hochbaum.