Lesson 20: Network Algorithms and Approximations by Mohammad Hajiaghayi: Metric Facility Location
Mohammad Hajiaghayi · 67:48 · Watch on YouTube
The lecture shows that metric uncapacitated facility location (UFL) has a constant-factor approximation. It uses LP rounding in two steps. First it "filters" the fractional solution so every client is served only by n...