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 2018	Heiko Röglin
Ü2			23. Oktober 2018	Anna Großwendt

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

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