Abschnitt Name Beschreibung
Vorlesungsfolien Datei 1. Vorlesung (22.10.) - Einführung und VertexCover

Einführung

Datei 1. Vorlesung - Druckversion

1. Vorlesung - Druckversion

Textseite 1. Vorlesung (Video)
Datei 2. Vorlesung (29.10.) - Greedy für SetCover und Anwendung auf ShortestSuperString

2. Vorlesung (29.10.)

Datei 2. Vorlesung - Druckversion

2. Vorlesung - Druckversion

Textseite 2. Vorlesung (Video)
Datei 3. Vorlesung (04.11.) - SteinerTree, Approximationsbewahrende Reduktionen, Mehrwegeschnitte

3. Vorlesung

Datei 3. Vorlesung - Druckversion

3. Vorlesung - Druckversion

Textseite 3. Vorlesung (Video)
Datei 4. Vorlesung (09.11.) Lineare Programmierung und LP-Dualität

4. Vorlesung (09.11.)

Datei 4. Vorlesung - Druckversion

4. Vorlesung (Druckversion)

Textseite 4. Vorlesung (Video)
Datei 5. Vorlesung (19.11.) - LP-basierte Techniken am Beispiel SetCover
Datei 5. Vorlesung (Druckversion)

5. Vorlesung (Druckversion)

Textseite 5. Vorlesung (Video)
Datei 6. Vorlesung (26.11.) - k-Center via parametrisches Pruning
Datei 6. Vorlesung (Druckversion)

6. Vorlesung (Druckversion)

Textseite 6. Vorlesung (Video)
Datei 7. Vorlesung (03.12.) - Scheduling via Parametrisches LP-Pruning
Datei 7. Vorlesung (Druckversion)

7. Vorlesung (Druckversion)

Textseite 7. Vorlesung (Video)
Datei 8. Vorlesung (10.12.) - FPTAS für Rucksackproblem via dynamischer Programmierung und Rundung

8. Vorlesung (10.12.)

Datei 8. Vorlesung (Druckversion)

8. Vorlesung (Druckversion)

Textseite 8. Vorlesung (Video)
Datei 9. Vorlesung (17.12.) - PTAS für Euklidisches TSP via Dynamischer Programmierung und Rundung

9. Vorlesung

Datei 9. Vorlesung (Druckversion)

9. Vorlesung (Druckversion)

Textseite 9. Vorlesung (Video)
Datei 10. Vorlesung (14.01.) - Min-Grad-Spannbaum via lokale Suche

10. Vorlesung

Datei 10. Vorlesung (Druckversion)

10. Vorlesung (Druckversion)

Textseite 10. Vorlesung (Video)
Datei 11. Vorlesung (21.01.): MaxSAT via Randomisiertes LP-Runden, Derandomisierung

Datei 11. Vorlesung (Druckversion)

11. Vorlesung (Druckversion)

Textseite 11. Vorlesung (Video)
Datei 12. Vorlesung (28.01.) Steiner-Wald via Primal-Dual-Ansatz

12. Vorlesung (28.01.)

Datei 12. Vorlesung (Druckversion)

12. Vorlesung (Druckversion)

Textseite 12. Vorlesung (Video)
Übungsblätter (Exercise Sheets) Datei LaTeX Template for exercise submissions