This is an old revision of the document!


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
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

Inhalt

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. Dezember3 Das k-Server-Problem
3.1 Einführende Bemerkungen
3.1.1 Der Greedy-Algorithmus
3.2 Untere Schranke für deterministische Algorithmen
11. Dezember3.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

Übungen

Prüfungen

Die mündlichen Prüfungen werden am 30. Januar sowie am 4. und 6. Februar 2020 stattfinden. Bitte wenden Sie sich an Frau Andrade zur Vereinbarung eines Prüfungstermins.

Literatur

Die Inhalte der Vorlesung basieren auf den beiden Skripten zu Approximationsalgorithmen und Online-Algorithmen.


Page Tools