WS24_Approx: Arbeitsmaterial

Abschnitt	Name	Beschreibung
Lecture Slides	01. Vorlesung: Einführung und VertexCover	Einführung
	01. Vorlesung: Druckversion
	02. Vorlesung: Greedy-Algorithmus für SetCover und Anwendung auf ShortestSuperString
	02. Vorlesung: Druckversion
	03. Vorlesung: Steinerbaum, approximationsbewahrende Reduktion, Mehrwegeschnitt	3. Vorlesung
	03. Vorlesung: Druckversion
	4. Vorlesung: Lineare Programmierung und LP-Dualität
	4. Vorlesung: Druckversion	4. Vorlesung (Druckversion)
	5. Vorlesung: LP-basierte Techniken am Beispiel SetCover
	5. Vorlesung: Druckversion
	6. Vorlesung: k-Center via parametrisches Pruning
	6. Vorlesung: Druckversion
	7. Vorlesung: Ablaufplanung via Parametrisches Pruning
	7. Vorlesung: Druckversion
	8. Vorlesung: FPTAS für das Rucksackproblem via dynamischer Programmierung und Rundung
	8. Vorlesung: Druckversion
	9. Vorlesung: PTAS für Euklidisches TSP via Dynamische Programmierung	9. Vorlesung
	9. Vorlesung: Druckversion
	10. Vorlesung: Spannbäume mit kleinstem Maximalgrad via lokale Suche	10. Vorlesung
	10. Vorlesung: Druckversion
	11. Vorlesung: MaxSAT via Randomisiertes LP-Runden, Derandomisierung
	11. Vorlesung: Druckversion
	12. Vorlesung: Steiner-Wald via Primal-Dual-Ansatz
	12. Vorlesung: Druckversion
	13. Vorlesung: Coloring Mixed Interval Graphs
	13. Vorlesung: Druckversion

Übungsblätter (Exercise Sheets)	LaTeX Template for exercise submissions