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.

 

tspicon1

 

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 nc 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 NP-Complete, so solving it has the same effect as solving the general TSP problem.

For example, if all of the cities lie on the x-axis 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 y-axis 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 n2. 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.

 

tspicon1

 

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 Information

The x-and-y-axes travelling salesman problem (paywalled)

First three pages of the paper

Related Articles

Travelling Salesman - A Movie About P=NP

The Physical Travelling Salesman Challenge

NP-Complete - Why So Hard?

Minimum Spanning Tree

Computational Complexity

 

blog comments powered by Disqus

 

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.

 

Banner


Python 2.7 To Be Maintained Until 2020
14/04/2014

The End of Life date of Python 2.7 has been extended by 5 years to 2020 to accommodate users who can't yet migrate to the Python 3. Although some Pythonistas are relieved by this news, others are infu [ ... ]



MariaDB 10 Available
10/04/2014

The stable version of MariaDB 10 has been released with better performance and new features. One major change is support for data in non-relational databases courtesy of the new Connect engine.


More News

 

Last Updated ( Saturday, 15 September 2012 )
 
 

   
RSS feed of news items only
I Programmer News
Copyright © 2014 i-programmer.info. All Rights Reserved.
Joomla! is Free Software released under the GNU/GPL License.