WS21_WS21_approx: Arbeitsmaterial

Abschnitt	Name	Beschreibung
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