Section Name Description
Vorlesungsfolien File 01. Vorlesung: Einführung und VertexCover

Einführung
File 01. Vorlesung: Druckversion
File 02. Vorlesung: Greedy-Algorithmus für SetCover und Anwendung auf ShortestSuperString
File 02. Vorlesung: Druckversion
File 03. Vorlesung: Steinerbaum, approximationsbewahrende Reduktion, Mehrwegeschnitt

3. Vorlesung

File 03. Vorlesung: Druckversion
File 4. Vorlesung: Lineare Programmierung und LP-Dualität
File 4. Vorlesung: Druckversion

4. Vorlesung (Druckversion)
File 5. Vorlesung: LP-basierte Techniken am Beispiel SetCover
File 5. Vorlesung: Druckversion
File 6. Vorlesung: k-Center via parametrisches Pruning
File 6. Vorlesung: Druckversion
File 7. Vorlesung: Ablaufplanung via Parametrisches Pruning
File 7. Vorlesung: Druckversion
File 8. Vorlesung: FPTAS für das Rucksackproblem via dynamischer Programmierung und Rundung
File 8. Vorlesung: Druckversion
File 9. Vorlesung: PTAS für Euklidisches TSP via Dynamische Programmierung

9. Vorlesung
File 9. Vorlesung: Druckversion
File 10. Vorlesung: Spannbäume mit kleinstem Maximalgrad via lokale Suche

10. Vorlesung
File 10. Vorlesung: Druckversion
File 11. Vorlesung: MaxSAT via Randomisiertes LP-Runden, Derandomisierung
File 11. Vorlesung: Druckversion
File 12. Vorlesung: Steiner-Wald via Primal-Dual-Ansatz
File 12. Vorlesung: Druckversion
File 13. Vorlesung: Mixed Interval Graphs
File 13. Vorlesung: Druckversion
File 13. Vorlesung: Containment Interval Graphs
Übungsblätter (Exercise Sheets) File LaTeX Template for exercise submissions