English subtitles

← 19ps-04 Randomized Approximation Solution

Get Embed Code
1 Language

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

  1. The answer to this is actually N-1.
  2. So in the worst case, it still has to look through N-1 iterations,
  3. which is not really any better than any of our other algorithms.
  4. And let's take a look at an example of why that is.
  5. So let's say we have this star-shaped graph,
  6. and we can see that there is a single
  7. vertex cover that is better than any of the others.
  8. That is you pick this vertex in the middle,
  9. and that automatically covers every single edge,
  10. and no other possible vertex cover is going to be as good.
  11. So with our randomized algorithm, let's say that we pick an edge at random.
  12. Let's say we pick this one,
  13. and then we have to pick one of the two endpoints randomly.
  14. Now let's say we pick this one and add it to the cover.
  15. Well then we've only covered this edge,
  16. and then we start over and reiterate.
  17. And let's say we pick edges at random,
  18. and each time we pick the outer vertex.
  19. It's unlikely, but it can happen.
  20. Now if we do that, then we've had to go through N-1 iterations to get a cover,
  21. and we are going to get a not great cover either.
  22. Now if we do this, you can see that
  23. we've had to go through N-1 iterations to find this cover,
  24. and it has a remotely close to the K equal 1 cover
  25. that is actually optimal in this case.