| 17.10.2025 |
Introduction and Vertex Cover (25.10.25: added half-integrality) |
Lecture 01 |
[Vazirani, Chapter 1] |
| 24.10.2025 |
Set Cover and Shortest Superstring |
Lecture 02 |
[Vazirani, Chapter 2] |
| 31.10.2025 |
Steiner Tree, approximation-preserving reduction, Multiway Cut |
Lecture 03 |
[Vazirani, Chapters 3+4] |
| 07.11.2025 |
Linear programming and LP-duality |
Lecture 04 |
[Vazirani, Chapter 12] |
| 14.11.2025 |
LP-based methods for Set Cover |
Lecture 05 |
[Vazirani, Chapters 14+15] |
| 21.11.2025 |
Metric k-Center via parametric pruning |
Lecture 06 |
[Vazirani, Chapter 5] |
| 28.11.2025 |
Scheduling via parametric pruning |
Lecture 07 |
[Vazirani, Chapter 17] |
| 12.12.2025 |
An FPTAS for the Knapsack Problem (via scaling) |
Lecture 08 |
[Vazirani, Chapter 8] |
| 19.12.2025 |
A PTAS for Euclidean TSP (via dynamic programming) |
Lecture 09 |
[Vazirani, Chapter 11] |
| 16.01.2026 |
Spanning trees with small maximum degree (via local search) |
Lecture 10 |
[FR: J. Alg., 1994] |
| 23.01.2026 |
MaxSat via randomized rounding and derandomization |
Lecture 11 |
[Vazirani, Chapter 16] |
