# CTK Insights

• ## Pages

25 Dec

### In Pursuit of the Traveling Salesman

It's a rare pleasure to get a good book ahead of its planned publishing date. In Pursuit of the Traveling Salesman by William Cook that was expected at the beginning of 2012, was delivered yesterday right to my door. My first impression is that this is the sort of a book that are read in one sitting, from cover to cover. The book is clearly intended for the "general audience" and is sweetly written. The author has an obvious writer's streak.

The book narrates the history of the so called "Traveling Salesman Problem", TSP for short. Occasionally (and rather suitably for Christmas time) it is also known as the Santa Claus Problem. In its TSP incarnation, the problem is to find the shortest route that passes through a given number of cities. For Santa Claus it may be important to make the planned visits in the shortest time possible. When it comes to drilling points of contact on a printed board or a computer chip, it's crucial - to make the cheaper chips - that the robot arm that drills the holes moves in a shortest possible path.

Here's a portion of such an itinerary on a board

The whole picture is available elsewhere. In fact, the TSP has numerous practical applications of which helping campaigning politicians is the most trifling.

TSP is NP-complete, which makes it of fundamental importance in Computer Sciences. It is natural that finding an optimal route between 10 cities takes less time than finding an optimal route between 100 cities. As a rule, as the input for an algorithm grows in size so do the memory and time requirements needed to execute the algorithm. An algorithm is thought to be good if that dependency is expressed as a polynomial in the size of the problem and bad if the dependency is exponential. "P" in "NP-complete" stands for "Polynomial". "N" stands for "Non-deterministic". How?

This is one thing to solve a problem and another to check whether or not a submitted solution is correct. Problem whose solution can be checked in polynomial time are said to belong to the NP-class. Those whose solution can be found in polynomial time belong to the P-class. Are the two classes the same? If you still do not know that, The Clay Mathematics Institute has announced a \$1,000,000 prize for answering this question. The fact that TSP is NP-complete means that the existence of a polynomial time algorithm for its solution will imply N = NP. Every one is welcome to try his or her prowess.

The book In Pursuit of the Traveling Salesman is a first-hand and a first-class introduction into the evolution of TSP, with chapters devoted to related mathematics and algorithmic topics. TSP is really at the heart of much of the research and development of modern computer science, so the author leads the reader through the past and emerging landscape of relevant research up to the very end of the mapped territory. Reading the book looks like an exciting adventure, with the itinerary mapped for the reader by a master story-teller whose work squarely places him in the forefront of the TSP research.

In the words of W. Cook:

I plan to take the reader on a path that goes well beyond basic familiarity of the TSP, moving right up to current theory and state-of-the-art solution machinery.

For more information on TSP, check a dedicated site. Bill Cook made available a free iPhone application, Concorde TSP Solver, that solves the 24-year old 2392-city example in under 7 minutes on iPhone 4. At that time, a supercomputer has set up a new world record by solving the problem in 23 hours.