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

Vorlesung: Approximationsalgorithmen

Dozent: Amin Coja-Oghlan

Termine

Die Vorlesung entfällt am 14.04.2005.
VL Dienstag 13:00 - 15:00 (RUD 26, 1.303)
Donnerstag 13:00 - 15:00 (RUD 26, 1.303)

Zuordnung

  • Hauptstudium, Halbkurs
  • Theoretische Informatik

Inhalte und Lernziele

Zahlreiche fundamentale algorithmische Probleme sind NP-schwer. Fuer diese Probleme sind also keine effizienten Algorithmen bekannt, welche jede Probleminstanz optimal lösen. Gegenstand der Vorlesung sind daher effiziente Algorithmen, die zwar im allgemeinen keine optimale, aber doch eine "gute Näherungslösung" bestimmen. Im Mittelpunkt stehen kombinatorische Optimierungsprobleme wie

  • das Travelling Salesman Problem (TSP),
  • das Knapsack-Problem,
  • das Aussagenlogische Erfuellbarkeitsproblem (SAT),
  • das Graphenfaerbungsproblem,
  • das Cliquenproblem,
  • MAX CUT.

Die behandelten Algorithmen sind kombinatorisch oder beruhen auf Techniken der Linearen oder Semidefiniten Programmierung. Ziel der Vorlesung ist, Methodenkompetenz zum Entwurf von Approximationsalgorithmen zu vermitteln.

Voraussetzungen

  • Grundstudium

Literatur

  • Emden-Weinert, Hougardy, Kreuter, Prömel, Steger, Einführung in Graphen und Algorithmen
  • Vazirani, Approximation algorithms, Springer 2001
  • Groetschel, Lovasz, Schrijver, Geometric algorithms and combinatorial optimization, Springer 1988
zuletzt geändert am 20.12.2005 (alkox-www)