English subtitles

← 14-17 Take 2 Approximation Quality Solution

Get Embed Code
1 Language

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

  1. There's 2 correct answers here. The first one is very obvious. It's this one here.
  2. Because the algorithm, of course, returns the vertex cover and the vertex cover
  3. can never get smaller than K. But the really useful answer is this one here.
  4. The algorithm has chosen at most 2 K vertices where K would have been the
  5. optimum number. Because each time this loop is run, it chooses at least 1 vertex
  6. from the optimum solution. What that also means is that it chooses at most 1
  7. useless vertex that didn't have to be part of that solution. So the error that it makes
  8. is at most 1 extra vertex, but it can make that error at most K times.
  9. And for that reason, the algorithm chooses at most 2K vertices
  10. which means that although the Take 2 algorithm doesn't look very smart,
  11. it's actually a factor 2 approximation algorithm. It guarantees that
  12. the solution that it gives you is at most twice as big as an optimum solution.
  13. So let's now have a look at the algorithm that seems so sophisticated.