## ← Reductions And Approximation Algorithms - Intro to Theoretical Computer Science

• 2 Followers
• 22 Lines

### Get Embed Code x Embed video Use the following code to embed this video. See our usage guide for more details on embedding. Paste this in your document somewhere (closest to the closing body tag is preferable): ```<script type="text/javascript" src='https://amara.org/embedder-iframe'></script> ``` Paste this inside your HTML body, where you want to include the widget: ```<div class="amara-embed" data-url="http://www.youtube.com/watch?v=vD3Br68O27c" data-team="udacity"></div> ``` 1 Language

Showing Revision 2 created 05/25/2016 by Udacity Robot.

1. So let's investigate this a bit further. And for now, we'll be focusing on vertex cover and on independent set.
2. So let's say we're given a graph with N vertices, and we're looking at the smallest possible vertex cover,
3. so a minimum vertex cover for that graph. And for the largest possible independent set.
4. So a maximum independent set. So let's say the size of the minimum vertex cover for this graph here is K,
5. so some integer smaller than N. And then--and you know this from the reduction between vertex cover and independent set--
6. the largest possible independent set that we can find in this graph has size N minus K.
7. So now, instead of finding the smallest possible vertex cover, let's run the factor two approximation algorithm.
8. And that algorithm will give us some number, and that number is guaranteed to be less than or equal to 2k.
9. And what that means for the independent set, of course, is if we take those N vertices here
10. and take away those 2k vertices, then of course we still arrive at an independent set, and that independent set has a size of
11. at least N minus 2k. Because the size of the vertex cover and of the independent set always add up to N.
12. So this here would be the optimum solution, and this here would be what the vertex cover factor two approximation finds.
13. So what about the approximation factor? So you already know that for vertex cover we have a factor two approximation.
14. And the way you arrive at the two is, of course, since this is a minimization problem, you take what the approximation finds
15. and divide it by the size of the optimum solution. So it's basically 2k over k, and that's equal to two.
16. Now, what about independent set? So, independent set is a maximization problem.
17. So, for vertex cover, we took what the algorithm finds and divided it by the size of the optimum solution.
18. But that was because it was a minimization problem. For a maximization problem, given how we define approximation factors,
19. we'll have to do it just the other way around. So the approximation factor here is the size of the optimum solution
20. divided by what the approximation actually finds. So it's divided by N minus 2k, which is equal to one plus K over N minus 2k.
21. So the factor two approximation algorithm for vertex cover is actually a factor one plus K over N minus 2k
22. approximation algorithm for independent set.