English subtitles

← 16-03 Reductions And Approximation Algorithms

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