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