Тема Название Описание
Vorlesungsfolien Файл 1. Vorlesung (22.10.) - Einführung und VertexCover

Einführung

Файл 1. Vorlesung - Druckversion

1. Vorlesung - Druckversion

Страница 1. Vorlesung (Video)
Файл 2. Vorlesung (29.10.) - Greedy für SetCover und Anwendung auf ShortestSuperString

2. Vorlesung (29.10.)

Файл 2. Vorlesung - Druckversion

2. Vorlesung - Druckversion

Страница 2. Vorlesung (Video)
Файл 3. Vorlesung (04.11.) - SteinerTree, Approximationsbewahrende Reduktionen, Mehrwegeschnitte

3. Vorlesung

Файл 3. Vorlesung - Druckversion

3. Vorlesung - Druckversion

Страница 3. Vorlesung (Video)
Файл 4. Vorlesung (09.11.) Lineare Programmierung und LP-Dualität

4. Vorlesung (09.11.)

Файл 4. Vorlesung - Druckversion

4. Vorlesung (Druckversion)

Страница 4. Vorlesung (Video)
Файл 5. Vorlesung (19.11.) - LP-basierte Techniken am Beispiel SetCover
Файл 5. Vorlesung (Druckversion)

5. Vorlesung (Druckversion)

Страница 5. Vorlesung (Video)
Файл 6. Vorlesung (26.11.) - k-Center via parametrisches Pruning
Файл 6. Vorlesung (Druckversion)

6. Vorlesung (Druckversion)

Страница 6. Vorlesung (Video)
Файл 7. Vorlesung (03.12.) - Scheduling via Parametrisches LP-Pruning
Файл 7. Vorlesung (Druckversion)

7. Vorlesung (Druckversion)

Страница 7. Vorlesung (Video)
Файл 8. Vorlesung (10.12.) - FPTAS für Rucksackproblem via dynamischer Programmierung und Rundung

8. Vorlesung (10.12.)

Файл 8. Vorlesung (Druckversion)

8. Vorlesung (Druckversion)

Страница 8. Vorlesung (Video)
Файл 9. Vorlesung (17.12.) - PTAS für Euklidisches TSP via Dynamischer Programmierung und Rundung

9. Vorlesung

Файл 9. Vorlesung (Druckversion)

9. Vorlesung (Druckversion)

Страница 9. Vorlesung (Video)
Файл 10. Vorlesung (14.01.) - Min-Grad-Spannbaum via lokale Suche

10. Vorlesung

Файл 10. Vorlesung (Druckversion)

10. Vorlesung (Druckversion)

Страница 10. Vorlesung (Video)
Файл 11. Vorlesung (21.01.): MaxSAT via Randomisiertes LP-Runden, Derandomisierung

Файл 11. Vorlesung (Druckversion)

11. Vorlesung (Druckversion)

Страница 11. Vorlesung (Video)
Файл 12. Vorlesung (28.01.) Steiner-Wald via Primal-Dual-Ansatz

12. Vorlesung (28.01.)

Файл 12. Vorlesung (Druckversion)

12. Vorlesung (Druckversion)

Страница 12. Vorlesung (Video)
Übungsblätter (Exercise Sheets) Файл LaTeX Template for exercise submissions