Unit 11: LP-Based Approximation

This is an archived version of this module from Summer 2025.
Click here for the current iteration.

This unit covers

• (randomized) rounding approximation algorithms
• LP duality
• dual fitting
• primal-dual schema

Material

• preliminary slides

• lecture notes

• Video 11-1 (2025-07-15, 5:44): LP & ILP recap
  
• Video 11-2 (2025-07-15, 13:36): LP Rounding
  
• Video 11-3 (2025-07-15, 10:21): Randomized Rounding
  
• Video 11-4 (2025-07-15, 14:23): LP Duality
  
• Video 11-5 (2025-07-15, 6:18): Vertex Cover and Matching via Duality
  
• Video 11-6 (2025-07-16, 31:23): Dual Fitting
  
• Video 11-7 (2025-07-16, 19:45): 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.

---

Unit 10  ⋅  Syllabus