Randomisierte und approximative Algorithmen

Termine

Art Wann Wo Beginn Dozent
V4 Montag 12:15 - 13:45
Mittwoch 12:15 - 13:45
CP1-HSZ / Hörsaal 3
CP1-HSZ / Hörsaal 3
8. Oktober 2018 Heiko Röglin
Ü2 Dienstag 12:15 - 13:45
Mittwoch 16:15 - 17:45
Donnerstag 12:15 - 13:45
Seminarraum 2.050
Seminarraum 2.050
Seminarraum 2.050
16. Oktober 2018 Andreas Tönnis
Andreas Tönnis
Alexander Göke

Die Nachprüfungen werden am 18.03.2019 stattfinden. Bitte melden Sie sich bis spätestens zum 01.03.2019 bei Frau Andrade zur Vereinbarung eines Prüfungstermins.

Inhalt

In dieser Vorlesung werden wir uns mit dem Entwurf und der Analyse von Approximationsalgorithmen beschäftigen.

Datum Inhalt
8. Oktober 1 Einleitung
2 Greedy-Algorithmen
2.1 Vertex Cover
2.2 Set Cover
10. Oktober 2.3 Scheduling auf identischen Maschinen
2.4 Rucksackproblem
15. Oktober 3 Runden und dynamische Programmierung
3.1 Rucksackproblem
17. Oktober 3.2 Scheduling auf identischen Maschinen
22. Oktober 3.2 Scheduling auf identischen Maschinen (Fortsetzung)
24. Oktober 4 Randomisierte Approximationsalgorithmen
4.1 Grundlagen der Wahrscheinlichkeitsrechnung
4.2 Zufallsvariablen und Erwartungswerte
29. Oktober 4.3 Max-SAT
31. Oktober 5 Lineare Programmierung und Runden
5.1 Max-SAT
5. November 5.1 Max-SAT (Fortsetzung)
5.2 Facility Location ohne Kapazitäten
7. November 5.2 Facility Location ohne Kapazitäten (Fortsetzung)
12. November 5.4 Scheduling auf allgemeinen Maschinen
14. November 5.4 Scheduling auf allgemeinen Maschinen (Fortsetzung)
6 Semidefinite Programmierung und Runden
6.1 Semidefinite Programmierung
19. November 6.2 Maximum-Cut Problem
6.3 Max-2SAT
21. November 6.4 Correlation Clustering
7 Lokale Suche
7.1 Spannbäume mit minimalem Maximalgrad
26. November 7.1.1 Erster Algorithmus
28. November 7.1.2 Verbesserter Algorithmus
7.2 Facility Location ohne Kapazitäten
3. Dezember 7.2 Facility Location ohne Kapazitäten (Fortsetzung)
10. Dezember 8 Primal-Duale Algorithmen
8.1 Duale Lineare Programme
17. Dezember 8.2 Set Cover
8.3 Feedback Vertex Set
19. Dezember 8.3 Feedback Vertex Set (Fortsetzung)
8.4 Das Kürzeste-Wege-Problem
7. Januar 8.5 Steinerwaldproblem
9. Januar 9 Traveling-Salesman-Problem
9.1 Allgemeines TSP
9.2 Metrisches TSP
9.2.1 2-Approximationsalgorithmus
9.2.2 Christofides-Algorithmus
14. Januar 9.3 Euklidisches TSP
16. Januar 9.3 Euklidisches TSP (Fortsetzung)
21. Januar 9.3 Euklidisches TSP (Fortsetzung)
23. Januar 10 Untere Schranken für Approximierbarkeit

Übungen

Literatur

Die Inhalte der Vorlesung finden sich in diesem Skript.


Page Tools