English subtitles

← 14-07 Factor 2 Solution

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