Approximation algorithm for vertex cover using local ratio (aka layering)
This is not the standard vertex cover approximation based on maximal matchings (I have another video on this), but an algorithm using a different technique: local ratio.
In the book by Vijay Vazirani this technique is used in the chapter (and later chapters) about set cover, and is called Layering there. However, I start with a simpler version, which corresponds to Exercise 2.11, and then only briefly discuss degree-weighted functions.
Slides are based on slides of Reuven Bar-Yehuda.
00:00 Introduction
02:26 Local Ratio Algorithm
06:34 Local Ratio Theorem
09:38 Step-by-step example
12:12 Alternative choice for w1 (degree-weighted)
15:01 Proof of approximation factor for degree-weighted w1
17:31 Summary
Смотрите видео Approximation algorithm for vertex cover using local ratio (aka layering) онлайн без регистрации, длительностью часов минут секунд в хорошем качестве. Это видео добавил пользователь Algorithms Lab 29 Октябрь 2023, не забудьте поделиться им ссылкой с друзьями и знакомыми, на нашем сайте его посмотрели 808 раз и оно понравилось 11 людям.