This is the first video in a series on approximation algorithms. I briefly review the basic underlying concepts and then take a look at a two-approximation for minimum vertex cover.
00:00 Motivation
01:19 Vertex Cover
05:46 NP Optimization Problems
09:09 Approximation Algorithms
10:29 Approximation Algorithm for Vertex Cover
13:15 Lower Bound via Maximal Matchings
16:22 Pseudocode and summary for algorithms
17:24 Questions and tight examples
20:40 Max Matching vs Min Vertex Cover
22:00 Summary
Acknowledgments: Slides for approximation algorithms are mostly due to colleagues in Würzburg, in particular Joachim Spoerhase and Alexander Wolff. Thanks!