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
— to be added —
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.