In Pursuit of the Traveling Salesman by William Cook

Recently read an interesting book on the traveling salesman problem.  I initially expected the book to be aimed at a more general audience and have the depth of a typical popular science book, but the topics were much more technical.  The book is well-written and an entertaining read.  Assuming a motivated instructor who could explain the more technical details missing from the book, it could serve as a textbook for an advanced undergraduate course.  I think it would be a course I would have enjoyed as an undergraduate and one I would be excited to try and teach today.

The first three chapters discuss the history of the problem and its myriad applications.  Chapter 4 presents a broad overview of the general approaches to solving the TSP.  Chapter 5—with the introduction of linear programming—is when things really become interesting.  He also discusses the simplex method and briefly talks about integer programming.

These are concepts that I wasn’t introduced to until graduate school in Computer Science.  He does a good job of illustrating the ideas and demonstrates the method with a simple example.  However, from this point, I’m not sure how much a reader will get from the book without a strong mathematical or computational foundation.  He also introduces the reader to operations research and points to an interesting operations research blog (One particularly interesting post examines which country won the Olympics by setting up possible weights on the gold, silver, and bronze medal counts as a linear programming problem.  The “winner” is the country that owns the majority of the solution space.).

He ends with a discussion of human and animal solutions to the TSP and a review of artists who are motivated by the TSP.  The introduction of the reader to the idea of not just algorithmic solutions to problems, but “good” solutions is a strong point of the book.  The description of Turing Machines and P vs. NP is as good as any I have seen outside of traditional textbooks.

Readers are left with several open problems that could serve as a starting point for budding TSP researchers:

  • Is the Euclidean TSP in NP?
  • Is there an algorithm provably faster than the n22n result of Held-Karp?
  • Is there a polynomial time algorithm guaranteed to produce a tour no more than 1.5 times the optimal?

In the end, the book is not a comprehensive study of the TSP, but an introduction and high-level overview that does touch on specific theoretical and computational issues.  I was intrigued by the discussions in the book and I will be seeking out more detailed information about the ideas discussed in the book.  My guess is that was the true goal of the author.

Advertisements
This entry was posted in Book, Math Envy and tagged , , , , , . Bookmark the permalink.

3 Responses to In Pursuit of the Traveling Salesman by William Cook

  1. yangqiaolu says:

    So the traveling salesman is not what it means literally?

    • Actually, it is. While it can be thought of as an abstract mathematical problem, it does have a variety of applications. This problem and other variations are actually something a salesman would have to consider when planning his route. Ideally he would like to take the shortest path that visits every stop to save money and time. Typically the goal is to minimize distance, but other constraints can be set. For instance, UPS recently improved their delivery times and fuel usage by minimizing left turns. Prior to that, they would have been solving a TSP problem based solely on minimizing distance.

      You would be surprised at the number of applications. Remember that machine we saw in China for cutting up large posterboard? In order to minimize the distance the saw has to travel, it would also need to solve the TSP problem. You might be more interested in the artistic aspects though (http://www.oberlin.edu/math/faculty/bosch/tspart-page.html). By setting points (cities) in particular locations, TSP solutions have a particular appearance. Note that every image is created by drawing a single unbroken line.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s