Travelling salesman problem

The traveling salesman problem is a prominent illustration of a class of problems in computational complexity theory. The problem can be enounced as: Given a number of cities and the costs of travelling from one to the other, what is the cheapest roundtrip route that visits each city exactly once and then returns to the start city?

The most immediate answer would be to try all the combinations and see which one is cheapest, but given that the number of combinations is N! (the factorial of the number of cities), this solution becomes rapidly unpractical.

How fast are the best known deterministic algorithms?

The problem has been shown to be NP-Hard, and the decision version of it ("Given the costs and a number x, decide whether there is a roundtrip route cheaper than x") is NP-Complete.

The problem is of considerable practical importance, and various approximation algorithms, which "quickly" yield "good" solutions with "high" probability, have been devised. An approximative solution for 15112 cities in Germany was found in 2001 by Princeton University scholars, see http://www.math.princeton.edu/tsp/d15sol/

There is really only one reasonable algorithm to solve the traveling salesman problem, the nearest neighbour algorithm.