Prof. Dr. Michael Jünger

Vorlesung Algorithmen für NP-schwierige Probleme
Mo 10-11:30 Uhr im HS 301 Pohligstr. 1
Mi 10-11:30 Uhr im HS 301 Pohligstr. 1

In der Vorlesung behandeln wir Algorithmen der linearen (gemischt) ganzzahligen und kombinatorischen Optimierung. Der Schwerpunkt liegt in der exakten Lösung gemischt ganzzahliger Optimierungsprobleme durch Schnittebenen- und Branch-and-Bound Algorithmen sowie NP-schwieriger kombinatorischer Entscheidungs-/Optimierungsprobleme durch Branch-and-Cut-and-Price Algorithmen. Außerdem werden wir uns mit polynomiellen Approximationsalgorithmen für NP-schwierige Probleme beschäftigen. Die Grundwerkzeuge der Linearen Programmierung und der Komplexitätstheorie werden eingeführt. Im Laufe der Vorlesung werden wir eine Auswahl prominenter kombinatorischer Entscheidungs-/Optimierungsprobleme behandeln: Erfüllbarkeitsproblem, Handlungsreisendenproblem, Lineares Ordnungsproblem, Maximum-Schnitt-Problem, Knotenüberdeckungsproblem, Graphfärbungsproblem, Cliquenproblem, Stabile-Mengen-Problem, Rucksackproblem, Kistenpackungsproblem, Maschineneinsatzproblem. Die Diskussion der Algorithmen wird durch Implementierungshinweise und Besprechung einschlägiger Software sowie von Anwendungsbeispielen in Industrie, Wirtschaft und den Naturwissenschaften ergänzt.

Literatur Algorithmen für NP-schwierige Probleme

• George Nemhauser und Laurence Wolsey: Integer and Combinatorial Optimization, Wiley, 1988.
  
• Alexander Schrijver: Theory of Linear and Integer Programming, Wiley, 1986.
  
• Alexander Schrijver: Combinatorial Optimization, in: Serie Algorithms and Combinatorics, Springer, 2003.
  
• Georgio Ausiello et al.: Complexity and Approximation, Springer, 1999.
  

Übungen Algorithmen für NP-schwierige Probleme
(gemeinsam mit Dipl.-Math. Michael Schulz)
In den Übungen wird der Vorlesungsstoff vertieft. Schriftliche Übungsaufgaben werden unter Anleitung eines Tutors besprochen. Die Übungsgruppeneinteilung kann hier eingesehen werden. Die Übungsblätter stehen auf dieser Webseite (siehe rechts) zum Download bereit. Der Übungsbetrieb beginnt am 27. bzw. 29.10.08.

Klausur Algorithmen für NP-schwierige Probleme
Die Klausur findet am 02.02.09 10-13 Uhr in Hörsaal 301, Pohligstr. 1, statt. Mit bestandener Klausur werden, je nach Bedarf, ein Übungsschein oder 9 Kreditpunkte erworben.

Die Ergebnisse der Klausur können hier eingesehen werden. Die Klausureinsicht findet am Montag, den 16.02.09, von 15 bis 17 Uhr in Raum 508 des Pohlighauses statt.

Nachklausur Algorithmen für NP-schwierige Probleme
Die Nachklausur findet am 02.03.09 10-13 Uhr in Hörsaal 301, Pohligstr. 1, statt.

Die Ergebnisse der Klausur können hier eingesehen werden. Die Klausureinsicht findet am Freitag, den 06.03.09, von 10.30 bis 11.30 Uhr in Raum 508 des Pohlighauses statt.

Hinweis für Wirtschaftsinformatiker:
Die Anmeldung zur Klausur läuft über das Prüfungsamt Wirtschaftsinformatik.