Section Nom Description
Vorlesungsfolien Fichier 1. Vorlesung (22.10.) - Einführung und VertexCover

Einführung

Fichier 1. Vorlesung - Druckversion

1. Vorlesung - Druckversion

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

2. Vorlesung (29.10.)

Fichier 2. Vorlesung - Druckversion

2. Vorlesung - Druckversion

Page 2. Vorlesung (Video)
Fichier 3. Vorlesung (04.11.) - SteinerTree, Approximationsbewahrende Reduktionen, Mehrwegeschnitte

3. Vorlesung

Fichier 3. Vorlesung - Druckversion

3. Vorlesung - Druckversion

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

4. Vorlesung (09.11.)

Fichier 4. Vorlesung - Druckversion

4. Vorlesung (Druckversion)

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

5. Vorlesung (Druckversion)

Page 5. Vorlesung (Video)
Fichier 6. Vorlesung (26.11.) - k-Center via parametrisches Pruning
Fichier 6. Vorlesung (Druckversion)

6. Vorlesung (Druckversion)

Page 6. Vorlesung (Video)
Fichier 7. Vorlesung (03.12.) - Scheduling via Parametrisches LP-Pruning
Fichier 7. Vorlesung (Druckversion)

7. Vorlesung (Druckversion)

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

8. Vorlesung (10.12.)

Fichier 8. Vorlesung (Druckversion)

8. Vorlesung (Druckversion)

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

9. Vorlesung

Fichier 9. Vorlesung (Druckversion)

9. Vorlesung (Druckversion)

Page 9. Vorlesung (Video)
Fichier 10. Vorlesung (14.01.) - Min-Grad-Spannbaum via lokale Suche

10. Vorlesung

Fichier 10. Vorlesung (Druckversion)

10. Vorlesung (Druckversion)

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

Fichier 11. Vorlesung (Druckversion)

11. Vorlesung (Druckversion)

Page 11. Vorlesung (Video)
Fichier 12. Vorlesung (28.01.) Steiner-Wald via Primal-Dual-Ansatz

12. Vorlesung (28.01.)

Fichier 12. Vorlesung (Druckversion)

12. Vorlesung (Druckversion)

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