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 | 7. Oktober 2019 | Heiko Röglin |
Ü2 | Donnerstag 10:15 - 11:45 Freitag 10:15 - 11:45 Freitag 12:15 - 13:45 | Seminarraum 2.050 Seminarraum 2.050 Seminarraum 2.050 | 17. Oktober 2019 18. Oktober 2019 18. Oktober 2019 | Xianghui Zhong Anna Großwendt Anna Großwendt |
In dieser Vorlesung werden wir uns mit dem Entwurf und der Analyse von Approximations- und Online-Algorithmen beschäftigen. Zukünftig wird es die Online-Algorithmen nicht mehr als separate Vorlesung geben, sondern die Inhalte werden in diese Vorlesung einfließen.
Datum | Inhalt |
---|---|
Approximationsalgorithmen | |
7. Oktober | 1 Einleitung 2 Greedy-Algorithmen 2.1 Vertex Cover 2.2 Set Cover |
9. Oktober | 2.3 Scheduling auf identischen Maschinen 2.4 Rucksackproblem |
14. Oktober | 3 Runden und dynamische Programmierung 3.1 Rucksackproblem |
16. Oktober | 3.2 Scheduling auf identischen Maschinen |
21. Oktober | 3.2 Scheduling auf identischen Maschinen (Fortsetzung) 4 Randomisierte Approximationsalgorithmen |
23. Oktober | 4.1 Grundlagen der Wahrscheinlichkeitsrechnung 4.2 Zufallsvariablen und Erwartungswerte |
28. Oktober | 4.3 Max-SAT |
30. Oktober | 4.3 Max-SAT (Fortsetzung) 5 Lineare Programmierung und Runden 5.1 Max-SAT |
4. November | 5.1 Max-SAT (Fortsetzung) |
6. November | 5.2 Facility Location ohne Kapazitäten |
11. November | 5.2 Facility Location ohne Kapazitäten (Fortsetzung) 5.3 Scheduling auf allgemeinen Maschinen |
13. November | 5.3 Scheduling auf allgemeinen Maschinen (Fortsetzung) |
18. November | 6 Semidefinite Programmierung und Runden 6.1 Semidefinite Programmierung 6.2 Maximum-Cut Problem |
Online-Algorithmen | |
20. November | 1 Einleitung 2 Paging 2.1 Deterministische Algorithmen 2.1.1 Markierungsalgorithmen |
25. November | 2.1.2 Untere Schranken 2.2 Randomisierte Algorithmen 2.2.1 Potentialfunktionen |
27. November | 2.2.2 Analyse von RANDOM 2.2.3 Analyse von MARK |
2. Dezember | 2.2.4 Untere Schranke für randomisierte Online-Algorithmen |
9. Dezember | 3 Das k-Server-Problem 3.1 Einführende Bemerkungen 3.1.1 Der Greedy-Algorithmus 3.2 Untere Schranke für deterministische Algorithmen |
11. Dezember | 3.3 Das k-Server-Problem auf Linien und Bäumen 3.3.1 Analyse des DC-Algorithmus auf der Linie 3.3.2 Analyse des DC-Algorithmus auf Bäumen |
18. Dezember | 3.3.3 Anwendungen des DC-Algorithmus 4 Approximation von Metriken 4.1 Approximation durch Baummetriken 4.1.1 Hierarchische Partitionen und Baummetriken |
8. Januar | 4.1.1 Hierarchische Partitionen und Baummetriken 4.1.2 Erzeugung von hierarchischen Partitionen 4.1.3 Analyse des Streckungsfaktors |
13. Januar | 4.1.3 Analyse des Streckungsfaktors (Fortsetzung) 4.2 Anwendung auf das k-Server-Problem 6.2 Maschinen mit Geschwindigkeiten |
Approximationsalgorithmen | |
15. Januar | 8 Primal-Duale Algorithmen 8.1 Duale Lineare Programme |
20. Januar | 8.2 Set Cover 8.3 Feedback Vertex Set |
22. Januar | 8.3 Feedback Vertex Set (Fortsetzung) |
27. Januar | 8.4 Das Kürzeste-Wege-Problem |
Die Nachprüfungen werden am 24. März 2020 stattfinden. Bitte wenden Sie sich bis zum 14. März 2020 an Frau Andrade zur Vereinbarung eines Prüfungstermins.
Die Inhalte der Vorlesung basieren auf den beiden Skripten zu Approximationsalgorithmen und Online-Algorithmen.