Got a YouTube account?

New: enable viewer-created translations and captions on your YouTube channel!

English subtitles

← Reductions And Approximation Algorithms - Intro to Theoretical Computer Science

Get Embed Code
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.