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

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.


Unit 10  ⋅  Syllabus