Beginn: Dienstag, den 20.10.1998

Für viele Optimierungsprobleme, die in vielfältigen Varianten in der Praxis auftreten, sind nachweisbar keine optimalen Lösungen effizient berechenbar. Verschiedene dieser Probleme lassen sich leicht mit Graphen anschaulich beschreiben. So tritt etwa im Zusammenhang mit dem Chip-Design das Problem MAXCUT auf: bei einem gegebenen Graphen G = (V,E) möchte man die Punktmenge V so in zwei Mengen V₁ und V₂ zerlegen, daß möglichst viele Kanten zwischen den beiden Mengen verlaufen. Das Problem MAXCUT ist NP-schwer und man fragt daher, wie man gute Näherungslösungen erhalten kann. In dieser Vorlesung sollen verschiedene Methoden zur approximativen Lösung von Benchmarkproblemen behandelt werden. Neben schon fast klassischen Methoden wie Greedy-Strategien, lokaler Suche und Simulated Annealing werden hier neuere Methoden aus dem Bereich Computational Intelligence wie evolutionäre Strategien, Derandomisierung und Semidefinite Programmierung ausführlich vorgestellt. Gerade diese Techniken haben in den letzten Jahren zunehmendes Interesse hinsichtlich der Analyse der Approximierbarkeit von Optimierungsproblemen gefunden.

Als Voraussetzung sind Kenntnisse im Rahmen eines Vordiploms erwünscht.

Literatur: D.S. Hochbaum, Approximation Algorithms for NP-hard Problems, PWS Publishing Company, 1996. Weitere Literatur wird in der Vorlesung bekanntgegeben und in einem Semesterhandapparat bereitgestellt.