Randomisierte und approximative Algorithmen

Termine

Art Wann Wo Beginn Dozent(in)
V4 Montag 10:15 - 11:45
Mittwoch 10:15 - 11:45
AVZ III / HS 2
AVZ III / HS 2
16. Oktober 2017 Heiko Röglin
Ü2 Montag 12:15 - 13:45
Freitag 10:15 - 11:45
AVZ III / A121
LBH E.08
23. Oktober 2017 Anna Großwendt

Inhalt

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

Datum Inhalt
16. Oktober 1 Einleitung
2 Greedy-Algorithmen
18. Oktober 2 Greedy-Algorithmen
23. Oktober 3 Runden und dynamische Programmierung
3.1 Rucksackproblem
25. Oktober 3.2 Scheduling auf identischen Maschinen
30. Oktober 3.2 Scheduling auf identischen Maschinen (Fortsetzung)
6. November 4 Randomisierte Approximationsalgorithmen
4.1 Grundlagen der Wahrscheinlichkeitsrechnung
8. November 4.2 Zufallsvariablen und Erwartungswerte
13. November 4.3 Max-SAT
15. November 4.3 Max-SAT (Fortsetzung)
5 Traveling-Salesman-Problem
5.1 Allgemeines TSP
5.2 Metrisches TSP
20. November 5.3 Euklidisches TSP
22. November 5.3 Euklidisches TSP (Fortsetzung)
27. November 5.3 Euklidisches TSP (Fortsetzung)
29. November 6 Lineare Programmierung und Runden
6.1 Max-SAT
4. Dezember 6.1 Max-SAT (Fortsetzung)
11. Dezember 6.2 Facility Location ohne Kapazitäten
13. Dezember 6.2 Facility Location ohne Kapazitäten (Fortsetzung)
18. Dezember 6.3 k-Median Problem
20. Dezember 6.3 k-Median Problem (Fortsetzung)

Übungsblätter

Literatur

Die Inhalte der Vorlesung finden sich in diesem Skript, das im Laufe des Semesters noch erweitert wird.


Page Tools