|
|
 |
LS 2 HomeTeaching (German)  Winter 04/05Sommer 04Diplomarbeiten (pdf)Frühere SemesterService Travel Staff Contact PrivateExternal Links Universität DortmundComputer Science FacultyCollab. Research Center 531Collab. Research Center 475Research Cluster 1126Student Advisory
|
Wintersemester 2003/04
Vorlesung ApproximationsalgorithmenDozent: Thomas Hofmeister
Termine:
Infos zur VorlesungDas 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.LinksEin 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 VorlesungFü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. |