Abschnitt: Vorlesungsfolien | WS22: Approximationsalgorithmen

Abschnittsübersicht

In der Tabelle unten liefert ein Klick aufs jeweilige Datum die Druckversion der Folien; ein Klick aufs Thema die Langversion.
Die Videos sind von Joachim Spoerhase aus den Corona-Jahren.

Datum	Thema	Videos (alt!)	Literatur
21.10.2022	Einführung und Vertex Cover	01. Vorlesung	[V, Kap. 1]
28.10.2022	Set Cover und Shortest Superstring	02. Vorlesung	[V, Kap. 2]
04.11.2022	Steinerbaum, approximationserhaltende Reduktion, Mehrwegeschnitt	03. Vorlesung	[V, Kap. 3+4]
18.11.2022	Lineare Programmierung und LP-Dualität	04. Vorlesung	[V, Kap. 12]
26.11.2022	LP-basierte Methoden für Set Cover	05. Vorlesung	[V, Kap. 14+15]
02.12.2022	Metrisches k-Zentrum mittels parametrischem Beschneiden	06. Vorlesung	[V, Kap. 5]
16.12.2022	Ablaufplanung mittels parametrischem Beschneiden	07. Vorlesung	[V, Kap. 17]
23.12.2022	Ein FPTAS für das Rucksackproblem (mittels Skalieren)	08. Vorlesung	[V, Kap. 8]
20.01.2023	Ein PTAS für euklidisches TSP (via dynamische Programmierung)	09. Vorlesung	[V, Kap. 11]
27.01.2023	Spannbäume mit kleinstem Maximalgrad (via lokale Suche)	10. Vorlesung	[FR: J. Alg., 1994]
03.02.2023	MaxSat via randomisiertes Runden und Derandomisierung	11. Vorlesung	[V, Kap. 16]
10.02.2023	Steinerwald via Primal-Dual-Ansatz	12. Vorlesung	[V, Kap. 22]