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 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 n². 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.