English subtitles

← 15-14 Algorithm Approximation Factor Solution

Get Embed Code
1 Language

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

  1. And the approximation factor here is a 2,
  2. because the length of the shortest tour
  3. is larger than the weight of the tree.
  4. And the solution that we output is twice the weight of the tree,
  5. so it must lie somewhere in between here,
  6. which tells you that this solution here
  7. is at most twice as large as an optimum solution.
  8. So Dave can now be very happy
  9. because he has a factor 2 approximation algorithm for his problem.
  10. Which, of course, should he ask you,
  11. you can easily explain to him, because you figured out most of this by yourself.