English 字幕

← 15-13 Algorithm Approximation Factor

埋め込みコードを取得する
1言語

字幕を編集する
ダウンロードする

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

  1. So now that we have 3 pieces of information,
  2. let's put these pieces together.
  3. So the first two that we will put together
  4. is the statement here on the second line
  5. and this one here on the third line.
  6. So we know that the length of the tour computed by the algorithm
  7. is exactly two times the weight of the minimum spanning tree.
  8. Now we will use the piece of information that we will have up here,
  9. so let's make a little bit more space down here.
  10. We know that the length of the shortest tour is larger than
  11. the weight of the minimum spanning tree,
  12. so we can put this part down here.
  13. Now isn't that beautiful.
  14. At least I think so.
  15. So the length of the shortest tour must lie somewhere
  16. in between the weight of the minimum spanning tree
  17. and the solution that you have just computed,
  18. which is twice the weight of the spanning tree.
  19. And this means that the algorithm I specified here is actually
  20. a constant factor approximation algorithm for shortest tour.
  21. Oh, I forgot to write the factor here.
  22. Well, of course I did that deliberately
  23. because this is going to be your final quiz
  24. for this algorithm.
  25. Please tell me what is the approximation factor,
  26. using this information we've just figured out,
  27. that this algorithm has for shortest tour?