Greedy Approximation Algorithm for Set Cover
In this video I introduce set cover, show a greedy approximation algorithm for computing the min-cost set cover, and analyze this algorithm. At the end, we look at vertex cover as a special case of set cover.
00:00 The Set Cover Problem
03:11 greedy algorithm for set cover
08:49 analysis of the greedy algorithm
10:27 proof of Lemma
14:06 proof of Theorem
16:33 Tightness
19:28 Vertex cover as set cover problem
Acknowledgments: Slides for approximation algorithms are mostly due to colleagues in Würzburg, in particular Joachim Spoerhase and Alexander Wolff. Thanks!