Lesson 22: Network Algorithms and Approximations by Mohammad Hajiaghayi: Iterative Rounding Method 1
Mohammad Hajiaghayi · 69:02
This lecture introduces iterative rounding and iterative relaxation, LP-based methods for approximation algorithms that started with Kamal Jain's 1998 work. The key claim is that an extreme-point (basic feasible) LP s...