Algorithmen und Komplexität - Hauptseite Algorithmen und Komplexität

Vorlesung: Kombinatorische Optimierung

Dozenten: Deryk Osthus und Anusch Taraz

Termine

Beginn der Vorlesung: 14.04.2004
VL Mittwoch 13:00 - 15:00 (RUD 26, 1.308)
Freitag 11:00 - 13:00 (RUD 26, 1.308)
Zu dieser Vorlesung gibt es ein Skript.

Zuordnung

  • Hauptstudium, Halbkurs
  • Theoretische Informatik

Voraussetzungen

  • Grundstudium

Inhalte und Lernziele

Das bekannteste kombinatorische Optimierungsproblem ist sicherlich das Travelling Salesman Problem - kombinatorische Optimierungsprobleme treten jedoch auch in vielen weiteren Bereichen auf. In dieser Vorlesung werden die wichtigsten Lösungsverfahren für solche Probleme vorgestellt und analysiert; unter anderem auch randomisierte und geometrische Verfahren.

Folgende Themen werden behandelt.
  • Branch and Bound
  • Dynamische Programmierung
  • Simulated Annealing
  • Online-Algorithmen
  • Lineare Programmierung
  • Polyedrische Optimierung
  • Semidefinite Programmierung
  • Scheduling

Empfohlene Literatur

  • W. Cook, W. Cunningham, W. Pulleyblank und A. Schrijver, Combinatorial Optimization, Wiley-Interscience 1998
  • B. Korte und J. Vygen, Theory and Algorithms, Springer Verlag, 2000
  • C.H. Papadimitriou und K. Steiglitz, Combinatorial Optimization: Algorithms and Complexity, Dover Publications, 1998
  • A. Schrijver, Combinatorial Optimization, Springer Verlag, 2003
zuletzt geändert am 23.01.2006 (alkox-www)