The XY Traveling Salesman Problem Solved 
Written by Mike James  
Friday, 14 September 2012  
The traveling salesman problem is important because it is NP complete.If you can find a fast way to solve it, you have proved P=NP and changed the face of computation. The latest result shows that a special type of traveling salesman (TSP) problem is solvable in polynomial time.
The TSP problem is easy to state but difficult to solve efficiently . All you have to do is to find the shortest route a salesman would have to travel to visit each of n cities. It turns out that no algorithm that is polynomial (i.e. takes time proportional to n^{c} where c is a constant) has been found. This form of the TSP is NP Hard and the decision version, which just has to decide if there is a solution better than a supplied sample tour, is NP Complete. What this means is that solving the decision version in polynomial time would provide a fast solution to all NP problems. This is not only theoretically interesting but of practical importance as public key cryptography depends on there being no such solution as it is based on a problem  factoring large numbers  that is also in NP. You can think of TSP as being the big computational problem of computer science, but despite a lot of work not a great deal of progress has been made  unless you count special cases. The Euclidean form of the problem simply places the cities on an xy grid and allows the salesman to travel by the straightest route between each city, i.e. as the bird flies rather than along roads. You might not think that the Euclidean form is any easier, and you would be correct, but you can add some more constraints. The Euclidean TSP is NPComplete, so solving it has the same effect as solving the general TSP problem. For example, if all of the cities lie on the xaxis then you can find a fast solution. In fact you can take this a stage further  if the cities lie on any reasonable curve you can compute a solution in polynomial time. This is interesting, but the restricted problem isn't NP complete and we need to try to loosen the conditions. The reason that the TSP on a curve is simpler is that the cities are arranged in one dimension. This suggests looking at a restricted 2D problem  the simplest of which is the XY TSP which constrains the cities to sit on the x or yaxis or on any two straight lines at right angles. The XY TSP problem has been studied since 1980 without much progress  until Vladimir Deineko (Warwick Business School), Eranda Cela (University of Technology Graz) and Gerhard Woeginger (Eindhoven University) invented a polynomial algorithm. The new algorithm is about as fast as one could reasonably expect working in time proportional to n^{2}. The algorithm is a dynamic programming approach that makes use of rules that force you to take paths between cities in particular groups. Is there an algorithm that works faster? Is there any way to extend the algorithm to more general Euclidean TSP? For example, suppose you distort the arrangement just a little so that some of the cities aren't quite on the x or y axes? Could a perturbation approach work, or is there some fundamental difference as soon as the cities have a more general arrangement. This says as much about real world geometry as it does combinatorial graph theory.
The only problem is that the paper describing how it all works is behind a paywall and costs $31.50 to read  which is an ongoing disgrace. More InformationThe xandyaxes travelling salesman problem (paywalled) First three pages of the paper Related ArticlesTravelling Salesman  A Movie About P=NP The Physical Travelling Salesman Challenge
Comments
or email your comment to: comments@iprogrammer.info
To be informed about new articles on I Programmer, install the I Programmer Toolbar, subscribe to the RSS feed, follow us on, Twitter, Facebook, Google+ or Linkedin, or sign up for our weekly newsletter.


Last Updated ( Saturday, 15 September 2012 ) 