## ← 14-07 Factor 2 Solution

• 1 Follower
• 19 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=2Jk_NR92ts4" data-team="udacity"></div> ``` 1 Language

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

1. Now, the important thing to notice here is that clique is a maximization problem.
2. That is, we're trying to find a clique that is as large as possible.
3. So we have already found a clique with 100 vertices.
4. So an optimum solution has to contain at least 100 vertices,
5. because we already know that a clique of this size is contained in the input network.
6. So this time, this 1 over here is easy.
7. Now, what about the maximum number of vertices in an optimum solution?
8. There could be a clique that is bigger than 100 vertices, but we just haven't found it.
9. Well, since clique is a maximization problem, we have to plug it into this equation here.
10. So our solution was 100 vertices which is ≥ 1/C.
11. C is the approximation factor, 1/C x the optimum, and if we solve that equation,
12. we find out that the optimum solution contains ≤ 200 vertices.
13. So this gives you a good intuition: For a minimization problem,
14. a factor-2 approximation algorithm means that we could have found a smaller solution,
15. but it is limited by this factor-2, and for a maximization problem,
16. we could have found a larger solution, but this is also limited by this factor-2,
17. or, more precisely, by 1 over this factor of 2.
18. So the factor here kind of gives us a range that tells us,
19. in a worst case scenario, how far away we are from the optimum solution.