Lehr- und Forschungseinheit für Theoretische Informatik,
Institut für Informatik
der Ludwig-Maximilians-Universität München
zurück zum Inhaltsverzeichnis dieser Seite
Zahlreiche für die Theorie und Praxis der Informatik wichtige algorithmische Probleme sind Optimierungsprobleme, d.h. zu jedem input gibt es mehrere potentielle Lösungen, die mit einem Kosten- bzw. Nutzenmaß versehen sind. Gesucht sind Lösungen, bei denen dieses Maß minimal bzw. maximal wird. Die meisten dieser Probleme sind NP-schwer, effiziente Algorithmen, die stets eine optimale Lösung finden, können also nur existieren, falls P=NP gilt.
Daher betrachtet man Approximationsalgorithmen für solche Probleme, die Lösungen berechnen, die nur um einen (a priori abzuschätzenden) kleinen Fehlerbetrag vom Optimum abweichen. NP-schwere Optimierungsprobleme können sich bzgl. ihrer Approximierbarkeit sehr verschieden verhalten
In der Vorlesung sollen Prinzipien zum Entwurf von Approximationsverfahren vorgestellt, sowie die theoretischen Grundlagen zur Untersuchung der Unterschiede im Approximierbarkeitsverhalten von Optimierungsproblemen gelegt werden. Dabei lehnt sie sich stark an das unten genannte Lehrbuch, speziell die Kapitel 1–5, an.
Für Fragen und Diskussionen gibt es ein Forum, das wir regelmäßig lesen.
G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela und M. Protasi "Complexity and Approximation. Combinatorial optimization problems and their approximability properties", Springer Verlag 1999, ISBN 3-540-65431-3.
Das Buch ist als Ansichtsexemplar in der Institutsbibliothek
vorhanden, Signatur 1602 / THE 20 Aus 1.
Es gibt auch eine WWW-Seite
zu dem Buch.
V. Vazirani "Approximation Algorithms", Springer Verlag 2001, ISBN 3-540-65367-8.