• The Amara On Demand team is looking for native speakers of German, Japanese, Korean, Italian, Hindi and Dutch to help with special paid projects
Apply here Hide

## ← 19ps-04 Randomized Approximation Solution

• 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=yAFVBKvkBg4" data-team="udacity"></div> ``` 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.