Sidebar
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 | 8. Oktober 2018 | Heiko Röglin |
| Ü2 | Dienstag 12:15 - 13:45 Mittwoch 16:15 - 17:45 Donnerstag 12:15 - 13:45 | Seminarraum 2.050 Seminarraum 2.050 Seminarraum 2.050 | 16. Oktober 2018 | Andreas Tönnis Andreas Tönnis Alexander Göke |
Inhalt
In dieser Vorlesung werden wir uns mit dem Entwurf und der Analyse von Approximationsalgorithmen beschäftigen.
| Datum | Inhalt |
|---|---|
| 8. Oktober | 1 Einleitung 2 Greedy-Algorithmen 2.1 Vertex Cover 2.2 Set Cover |
| 10. Oktober | 2.3 Scheduling auf identischen Maschinen 2.4 Rucksackproblem |
| 15. Oktober | 3 Runden und dynamische Programmierung 3.1 Rucksackproblem |
| 17. Oktober | 3.2 Scheduling auf identischen Maschinen |
| 22. Oktober | 3.2 Scheduling auf identischen Maschinen (Fortsetzung) |
| 24. Oktober | 4 Randomisierte Approximationsalgorithmen 4.1 Grundlagen der Wahrscheinlichkeitsrechnung 4.2 Zufallsvariablen und Erwartungswerte |
| 29. Oktober | 4.3 Max-SAT |
| 31. Oktober | 5 Lineare Programmierung und Runden 5.1 Max-SAT |
| 5. November | 5.1 Max-SAT (Fortsetzung) 5.2 Facility Location ohne Kapazitäten |
| 7. November | 5.2 Facility Location ohne Kapazitäten (Fortsetzung) |
| 12. November | 5.4 Scheduling auf allgemeinen Maschinen |
| 14. November | 5.4 Scheduling auf allgemeinen Maschinen (Fortsetzung) 6 Semidefinite Programmierung und Runden 6.1 Semidefinite Programmierung |
| 19. November | 6.2 Maximum-Cut Problem 6.3 Max-2SAT |
| 21. November | 6.4 Correlation Clustering 7 Lokale Suche 7.1 Spannbäume mit minimalem Maximalgrad |
| 26. November | 7.1.1 Erster Algorithmus |
| 28. November | 7.1.2 Verbesserter Algorithmus 7.2 Facility Location ohne Kapazitäten |
| 3. Dezember | 7.2 Facility Location ohne Kapazitäten (Fortsetzung) |
| 10. Dezember | 8 Primal-Duale Algorithmen 8.1 Duale Lineare Programme |
| 17. Dezember | 8.2 Set Cover 8.3 Feedback Vertex Set |
| 19. Dezember | 8.3 Feedback Vertex Set (Fortsetzung) 8.4 Das Kürzeste-Wege-Problem |
| 7. Januar | 8.5 Steinerwaldproblem |
| 9. Januar | 9 Traveling-Salesman-Problem 9.1 Allgemeines TSP 9.2 Metrisches TSP 9.2.1 2-Approximationsalgorithmus 9.2.2 Christofides-Algorithmus |
| 14. Januar | 9.3 Euklidisches TSP |
| 16. Januar | 9.3 Euklidisches TSP (Fortsetzung) |
| 21. Januar | 9.3 Euklidisches TSP (Fortsetzung) |
| 23. Januar | 10 Untere Schranken für Approximierbarkeit |
Übungen
- Übungsblatt 1 (Besprechung in KW 42)
- Übungsblatt 2 (Besprechung in KW 43)
- Übungsblatt 3 (Besprechung in KW 44)
- Übungsblatt 4 (Besprechung in KW 45)
- Übungsblatt 5 (Besprechung in KW 46)
- Übungsblatt 6 (Besprechung in KW 47)
- Übungsblatt 7 (Besprechung in KW 48)
- Übungsblatt 8 (Besprechung in KW 49)
- Übungsblatt 9 (Besprechung in KW 50)
- Übungsblatt 10 (Besprechung in KW 51)
- Übungsblatt 11 (Besprechung in KW 2)
- Übungsblatt 12 (Besprechung in KW 3)
Literatur
Die Inhalte der Vorlesung finden sich in diesem Skript.