LP-based Approximation Algorithms for Set Cover: LP Rounding, Primal-Dual and Dual fitting
An introduction to approximation algorithms based on linear programming (LP) by the example of the set cover problem. The techniques that we cover are:
LP Rounding
Primal-Dual
Dual fitting (for the analysis of the greedy set cover algorithm)
00:00 Lower bounds from Linear Programming
04:17 Set Cover ILP
07:59 LP Rounding
09:50 Set Cover: Optimum vs Optimum of relaxed LP
11:13 First Attempt
12:30 Rounding based on frequency
16:05 LP Duality
17:36 Weak + Strong Duality
20:46 Complementary Slackness
23:22 Primal-Dual Method
25:42 The dual of Set Cover
28:05 Relaxed Complementary Slackness
29:45 Primal-Dual for Set Cover: Setup
32:24 Primal-Dual Algorithm for Set Cover
35:59 Tight Example + Integrality Gap
38:51 Dual Fitting
40:48 Greedy Set Cover
43:14 price(u) as dual variable + fitting
44:56 Lemma + proof
50:20 Summary