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

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
8.2 Set Cover
12. Dezember 8.2 Set Cover (Fortsetzung)
8.3 Feedback Vertex Set
17. Dezember 8.4 Das Kürzeste-Wege-Problem
8.5 Steinerwaldproblem
19. Dezember 8.5 Steinerwaldproblem (Fortsetzung)

Übungen

Prüfungen

Die mündlichen Prüfungen werden zwischen dem 30.01.2019 und dem 04.02.2019 stattfinden. Bitte melden Sie sich bei Frau Andrade zur Vereinbarung eines Prüfungstermins.

Literatur

Die Inhalte der Vorlesung finden sich in diesem Skript.


Page Tools