Two LP-based methods were covered. Filtering the optimal LP solution was illustrated to design a constant factor approximation for the metric uncapacitated facility location problem. The primal-dual method was illustrated by designing a 2-approximation algorithm for the generalized Steiner forest problem.
Filtering and the Primal-Dual Method – Part 1
