| 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 |
