2012-10-06

Travelling Salesman

The Travelling Salesman is a classic problem. Given n cities, and for each pair of them the time it takes to travel from one to the other, find the fastest way to visit all cities, without visiting any more than once, and then come back to the starting city. This problem is well known to be NP-complete. But there might be ways to simplify it a little. Since Bengt refuses to go on holiday if it can't be done in the most efficient way, and it's clear he needs to get out more, we should try to help him.

  1. Suppose the world is flat, cities are pointlike, and the time it takes to travel between them is proportional to the physical distance. Is it still NP-complete? Show that it is, or find a polynomial-time solution.
  2. What if the world is spherical? Does that make a difference?
  3. What if we have up to k dimensions? Or up to n dimensions?
  4. Going back to the flat world, what if some roads are a little bit slower, so that the time to move between two cities is between 1 and k times the distance? What if it's between 1 and n?
  5. Suppose we don't need to get back to the starting position. Does that make a difference? If not, why did they bother including that in the problem definition?
  6. (hard) Suppose we don't care about finding the quickest route, but we want to avoid being on the road (between two cities) for more than a day at a time. Is there a polynomial-time solution for that?