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!
Смотрите видео Approximation Algorithms: Introduction by the Example of Vertex Cover онлайн без регистрации, длительностью часов минут секунд в хорошем качестве. Это видео добавил пользователь Algorithms Lab 23 Октябрь 2023, не забудьте поделиться им ссылкой с друзьями и знакомыми, на нашем сайте его посмотрели 1,376 раз и оно понравилось 18 людям.