Secção: Vorlesungsfolien | WS23: Approximationsalgorithmen

Lista de secções

In the table below clicking on the date yields the printer version of the slides, clicking on the topic of a lecture yields the long version of the slides.
The videos were made by Joachim Spoerhase during Covid years. Enjoy!

Date	Topic	Videos (old!)	Literature
20.10.2023	Introduction and Vertex Cover	Lecture 01	[Vazirani, Chapter 1]
27.10.2023	Set Cover and Shortest Superstring [25.12.: added backslash to "alg." ;-)]	Lecture 02	[Vazirani, Chapter 2]
03.11.2023	Steiner Tree, approximation-preserving reduction, Multiway Cut	Lecture 03	[Vazirani, Chapters 3+4]
10.11.2023	Linear programming and LP-duality	Lecture 04	[Vazirani, Chapter 12]
17.11.2023	LP-based methods for Set Cover	Lecture 05	[Vazirani, Chapters 14+15]
24.11.2023	Metric k-Center via Parametric Pruning	Lecture 06	[Vazirani, Chapter 5]
01.12.2023	Scheduling via Parametric Pruning	Lecture 07	[Vazirani, Chapter 17]
08.12.2023	No lecture
15.12.2023	An FPTAS for the Knapsack Problem (via scaling)	Lecture 08	[Vazirani, Chapter 8]
22.12.2023	A PTAS for Euclidean TSP (via dynamic programming)	Lecture 09	[Vazirani, Chapter 11]
12.01.2024	Spanning Trees with Small Maximum Degree (via local search)	Lecture 10	[FR: J. Alg., 1994]
19.01.2024	MaxSat via randomized rounding and derandomization	Lecture 11	[Vazirani, Chapter 16]
26.01.2024	Steiner Forest via primal–dual scheme	Lecture 12	[Vazirani, Chapter 22]
02.02.2024	Coloring Directional and Containment Interval Graphs	Lecture 13	[Gutowski et al., GD 2022 and ISAAC 2023]
09.02.2024	No lecture