Approximation Algorithms: Introduction by the Example of Vertex Cover
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!
Watch video Approximation Algorithms: Introduction by the Example of Vertex Cover online without registration, duration hours minute second in high quality. This video was added by user Algorithms Lab 23 October 2023, don't forget to share it with your friends and acquaintances, it has been viewed on our site 1,376 once and liked it 18 people.