English subtitles

← 16-13 Travelling Salesman

Get Embed Code
1 Language

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

  1. Now, finally, what about Bob, who is solving Shortest Tour?
  2. Well, Shortest Tour is a problem that hasn't been investigated that much.
  3. In the general case, for it's closely related problem, Travelling Salesman,
  4. we don't know.
  5. But there are many special cases of this problem
  6. where good approximations are actually possible.
  7. But the bounds of approximation for Shortest Tour and Travelling Salesman
  8. have actually not been investigated that much.
  9. So if you're really into it, that will be a possible area for research.
  10. Although, it seems to be quite hard to actually transfer the results
  11. from here over to Shortest Tour.
  12. So maybe we can make Alice a little bit less happy;
  13. although, she has been quite lucky in this course.
  14. She has a constant factor approximation algorithm,
  15. and the limit of 1.36 probably doesn't affect her that much.
  16. And Bob, well, it's not really clear if he should be happy or not,
  17. but as we mentioned, in practice it's likely
  18. that his problem is actually very well solvable.