| 18.10.2024 |
Introduction and Vertex Cover |
Lecture 01 |
[Vazirani, Chapter 1] |
| 25.10.2024 |
Set Cover and Shortest Superstring |
Lecture 02 |
[Vazirani, Chapter 2] |
| 08.11.2024 |
Steiner Tree, approximation-preserving reduction, Multiway Cut |
Lecture 03 |
[Vazirani, Chapters 3+4] |
| 15.11.2024 |
Linear programming and LP-duality |
Lecture 04 |
[Vazirani, Chapter 12] |
| 22.11.2024 |
LP-based methods for Set Cover |
Lecture 05 |
[Vazirani, Chapters 14+15] |
| 29.11.2024 |
Metric k-Center via parametric pruning |
Lecture 06 |
[Vazirani, Chapter 5] |
| 06.12.2024 |
Scheduling via parametric pruning |
Lecture 07 |
[Vazirani, Chapter 17] |
| 13.12.2024 |
An FPTAS for the Knapsack Problem (via scaling) |
Lecture 08 |
[Vazirani, Chapter 8] |
| 10.01.2025 |
A PTAS for Euclidean TSP (via dynamic programming) |
Lecture 09 |
[Vazirani, Chapter 11] |
| 17.01.2025 |
Spanning Trees with Small Maximum Degree (via local search) |
Lecture 10 |
[FR: J. Alg., 1994] |
| 24.01.2025 |
MaxSat via randomized rounding and derandomization |
Lecture 11 |
[Vazirani, Chapter 16] |
| 31.01.2025 |
Steiner Forest via primal–dual scheme |
Lecture 12 |
[Vazirani, Chapter 22] |
| 07.02.2025 |
Coloring Mixed Interval Graphs |
Lecture 13 |
[Gutowski et al., GD 2022 and ISAAC 2023] |
