Approximationsverfahren für Optimierungsprobleme

Aktuelles

• Anmeldung über UniWorx ist jetzt freigeschaltet.

Inhalt

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:

• 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 Approximierbarkeitsverhalten von Optimierungsproblemen gelegt werden. Dabei lehnt sie sich stark an das unten genannte Lehrbuch, speziell die Kapitel 1–5, an.

Organisation

• Umfang: 3+1 Semesterwochenstunden
• Vorkenntnisse: Algorithmen und Datenstrukturen und Formale Sprachen und Komplexität bzw. Theoretische Informatik für Medieninformatiker
  
• Vorlesung & Übung: Dr. Jan Johannsen

• für Studierende im Studiengang Informatik Diplom im Prüfungsfach Programmierung und Grundlagen, Teilbereich Theoretische Informatik
  
• für Studierende im Studiengang Informatik Master für das Modul Algorithmik und Komplexität
  
• für Studierende im Studiengang Medieninformatik Master für das Modul Vertiefende Themen der Informatik für Master
  
• für Studierende in den Studiengängen Informatik und Medieninformatik Bachelor für das Modul Vertiefende Themen der (Medien-) Informatik
  
• für Studierende mit Nebenfach Informatik nach Vereinbarung

Zeit und Ort

Material zur Vorlesung

Vorlesungsfolien

• Kapitel 0: Einführung
• Kapitel 1: Grundlagen 
• Kapitel 2: Methoden zum Entwurf 
• Kapitel 3: Approximationsklassen
• Kapitel 4: Das PCP-Theorem
• Kapitel 5: Reduktion und Vollständigkeit
  

Literatur:

• 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.

Übungen

Die Übungen finden 14-tägig zum Vorlesungstermin am Donnerstag statt, zuerst am 27. Oktober.

Übungsblätter

• Blatt 1 vom 27.10.
• Blatt 2 vom 15.11
• Blatt 3 vom 01.12.
• Blatt 4 vom 15.12.
• Blatt 5 vom 26.01.
  

Klausur

Die Klausur findet in der letzten Übung am 9. Februar um 16 Uhr statt.