## ← 16-03 Reductions And Approximation Algorithms

• 1 Follower
• 25 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=53bN-yEyi7c" data-team="udacity"></div> 1 Language

Showing Revision 1 created 10/03/2012 by Amara Bot.

1. So let's investigate this a little bit further,
2. and we'll focus on vertex cover and independent set for now.
3. So let's say we have as input a graph with N vertices.
4. Now let's say we compute a minimum vertex cover for that graph,
5. and that vertex cover has size K.
6. Then as you remember from the reduction,
7. we know that the largest independent set
8. in the same graph has size N minus K.
9. If we use the approximation algorithm for vertex cover,
10. then that algorithm will find a vertex cover
11. that is at most 2K in size.
12. What that means for independent set,
13. if we use the same approximation algorithm,
14. that we know that the graph has an independent set
15. of size at least N minus 2K.
16. So this is what the approximation finds,
17. and this here is an optimum solution.
18. It means that over here we have a factor to approximation, as you remember.
19. Now over here, to figure out the approximation factor,
20. we have to divide what the algorithm finds
21. by the size of an optimum solution,
22. which is equal to 1 minus K over N minus K.
23. So the factor to approximation algorithm for vertex cover
24. is a factor 1 minus K over N minus K
25. approximation algorithm for independent set.