Wintersemester 2003/04

Vorlesung Approximationsalgorithmen

Dozent: Thomas Hofmeister

Termine:
Di. 12:15-13:45 Uhr, GB 4, 318
Mi. 14.15-15:45 Uhr, GB 4, 112

Infos zur Vorlesung

Das Skript, das durch die einzelnen Mitschriften entstanden ist, kann bei uns von den Teilnehmern/innen an der Vorlesung abgeholt werden. Ich halte erst einmal 5 Ausdrucke parat, wenn es dann weniger werden, drucke ich Nachschub.

Was wurde wann gemacht?

Links

Ein Skript zu einer Vorl. an der John Hopk. Univ.

Die Ergebnisse zu Greedy-Algorithmen für das Independent Set Problem stammen aus einem Papier von Halldorsson und Radhakrishnan. Inhalt findet man z.B. in diesem Aufschrieb.

Einige der präsentierten Resultate zu Maxcut findet man in diesem Papier

Paper zu "Weighted Vertex Cover"

Skript Approximationsalgorithmen Rolf Wanka

Motwani: Lecture Notes on Approx. Algorithms bzw. hier

Williamson: Lecture Notes on Approx. Algorithms (steht unten unter Course Notes)

Gegenstand der Vorlesung

Für sehr viele wichtige Optimierungsprobleme sind keine Polynomialzeitalgorithmen bekannt, die das Problem exakt lösen. Dann bieten sich Algorithmen an, die zwar nicht das Optimum finden, aber Lösungen, die dicht am Optimum liegen, so genannte Approximationsalgorithmen. Um diese geht es in dieser Vorlesung, die, wie auch die entsprechende Literatur, problemorientiert ist, das heißt, pro "Kapitel" wird jeweils ein bestimmtes Problem behandelt und einige für das Problem existierende Approximationsalgorithmen vorgestellt. Vorkenntnisse aus der Vorlesung "Effiziente Algorithmen" sind hilfreich, aber nicht notwendig. Grundlage der Vorlesung sind (u.a.) die Bücher "Approximation Algorithms" von V.V. Vazirani und "Approximation Algorithms for NP-hard Problems" von D.S. Hochbaum.