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)
8. Januar 6.4 Scheduling auf allgemeinen Maschinen
10. Januar 6.4 Scheduling auf allgemeinen Maschinen (Fortsetzung)
7 Semidefinite Programmierung und Runden
7.1 Semidefinite Programmierung
15. Januar 7.1 Semidefinite Programmierung (Fortsetzung)
7.2 Maximum-Cut Problem
17. Januar 7.3 Max-2SAT
7.4 Correlation Clustering
22. Januar 7.4 Correlation Clustering (Fortsetzung)
8 Untere Schranken für Approximierbarkeit
8.1 Reduktionen von NP-schweren Problemen
24. Januar 8.2 Reduktionen mithilfe des PCP-Theorems

Übungsblätter

Prüfungen

Die Nachprüfungen werden am 26. März stattfinden. Bitte melden Sie sich möglichst bald bei Frau Andrade, um einen Prüfungstermin zu vereinbaren.

Literatur

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


Page Tools