main page — CS 627 Advanced Algorithms
Unit 11: LP-Based Approximation
This unit covers
- (randomized) rounding approximation algorithms
- LP duality
- dual fitting
- primal-dual schema
Material
- preliminary slides
- Video 11-1 (2025-07-15):
LP & ILP recap
- Video 11-2 (2025-07-15):
LP Rounding
- Video 11-3 (2025-07-15):
Randomized Rounding
- Video 11-4 (2025-07-15):
LP Duality
- Video 11-5 (2025-07-15):
Vertex Cover and Matching via Duality
- Video 11-6 (2025-07-16):
Dual Fitting
- Video 11-7 (2025-07-16):
Primal-Dual Schema
Further reading and sources
The presentation mostly follows
- Vazirani, Vijay V. “Approximation Algorithms.” Springer, 2001.
Examples are also taken from Advanced Algorithms, following the module in Kaiserslautern initially developed by Markus Nebel.