Lehr- und Forschungseinheit für Theoretische Informatik,
Institut für Informatik
der Ludwig-Maximilians-Universität München
Vorlesung im Hauptstudium (WS 00/01):
Approximationsverfahren für Optimierungsprobleme
- Vorlesung:
-
Dr. Jan Johannsen, 4-stündig
- Zeit und Ort: Mi 13.00 - 14.30, Fr 11.30 - 13.00, Raum 0.41
- Beginn: 18. 10. 2000
- Übung:
-
Dr. Jan Johannsen, 2-stündig
- Zeit und Ort der Übung: Di 11.15 - 12.45, Raum Z1.09
- Beginn: 31. 10. 2000
- Vorkenntnisse:
- Grundkenntnisse in Informatik
- Hörerkreis: :
- Studierende im Hauptstudium der Informatik
- Studierende mit Nebenfach Informatik
- Schein:
- bei ausreichender Bearbeitung von Hausaufgaben
und mündlicher Prüfung.
- Schein gilt für Diplomprüfung in
Haupt- und Nebenfach Informatik
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-hart,
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-harte Optimierungsprobleme können sich bzgl. ihrer
Approximierbarkeit sehr verschieden verhalten
- für einige gibt es beliebig gute Approximationsverfahren;
- andere erlauben effiziente Approximationsverfahren bis zu einer gewissen
Güte, aber keine besseren;
- für einige besonders hartnäckige Probleme kann es
überhaupt kein effizientes Approximationsverfahren geben.
In der Vorlesung sollen Prinzipien zum Entwurf von
Approximationsverfahren vorgestellt, sowie die theoretischen
Grundlagen zur Untersuchung der Unterschiede im Approximierbarkeitsverhaltens
von Optimierungsproblemen gelegt werden.
Dabei lehnt sie sich stark an das unten genannte Lehrbuch, speziell
die Kapitel 1-5, an.
- Einführung
- Zur Erinnerung: Komplexität von Entscheidungsproblemen
- Komplexitätsklassen
- NP-vollständige Probleme
- Optimierungsprobleme
- Methoden zum Entwurf von Approximationsalgorithmen
- Greedy Algorithmen
- Sequentielle Algorithmen für Partitionierungsprobleme
- Lokale Suche
- Lineare Programmierung
- Dynamische Programmierung
- Approximierbarkeitsklassen
- Absolute Approximation
- Relative Approximation
- Approximationsschemata
- Das PCP-Theorem
- Probabilistisch überprüfbare Beweise (PCP)
- PCP-Charakterisierung von NP
- Nicht-Approximierbarkeit von Maximum Satisfiability und Maximum
Clique
- Zum Beweis des PCP-Theorems
- Approximationserhaltende Reduktionen
- AP-Reduktion und L-Reduktion
- NPO-vollständige Probleme
- APX-vollständige Probleme
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.
zurück zum
Inhaltsverzeichnis dieser Seite
zurück zum Inhaltsverzeichnis
dieser Seite