In Pursuit of the Traveling Salesman

In Pursuit of the Traveling Salesman is a book-length examination of the traveling salesman problem (TSP) in computer science, written by one of the foremost mathematicians working on solutions to the TSP. Cook is Professor of Applied Mathematics and Statistics at Johns Hopkins University and is one of the authors of the Concorde TSP Solver.

First, a brief summary of the TSP for readers without a CS background. While there are numerous variations, the traditional problem is this: given as input a list of coordinates on a two-dimensional map representing cities, construct a minimum-length path that visits each city exactly once and then returns to the starting city. It's famous in computer science in part because it's easy to explain and visualize but still NP-hard, which means that not only do we not know of a way to exactly solve this problem in a reasonable amount of time for large numbers of cities, but also that a polynomial-time solution to the TSP would provide a solution to a vast number of other problems. (For those familiar with computability theory, the classic TSP is not NP-complete because it's not a decision problem and because of some issues with Euclidean distances, but when stated as a graph problem and converted into a decision problem by, for example, instead asking if there is a solution with length less than n, it is NP-complete.)

This is one of those books where the quality of the book may not matter as much as its simple existence. If you're curious about the details of the traveling salesman problem specifically, but don't want to read a lot of mathematics and computer science papers, algorithm textbooks, or books on graph theory, this book is one of your few options. Thankfully, it's also fairly well-written. Cook provides a history of the problem, a set of motivating problems (the TSP doesn't come up as much and isn't as critical as some NP-complete problems, but optimal tours are still more common than one might think), and even a one-chapter tour of the TSP in art. The bulk of the book, though, is devoted to approximation methods, presented in roughly chronological order of development.

Given that the TSP is NP-hard, we obviously don't know a good exact solution, but I admit I was a bit disappointed that Cook spent only one chapter exploring the exact solutions and explaining to the reader what makes the problem difficult. Late in the book, he does describe the Held-Karp dynamic programming algorithm that gets the work required for an exact solution down to exponential in n, provides a basic introduction to complexity theory, and explains that the TSP is NP-complete by reduction from the Hamiltonian path problem, but doesn't show the reduction of 3SAT to Hamiltonian paths. Since my personal interest ran a bit more towards theory and less towards practical approximations, I would have appreciated a bit more discussion of the underlying structure of the problem and why it's algorithmically hard. (I did appreciate the explanation of why it's not clear whether the general Euclidean TSP is even in NP due to problems with square roots, though.)

That said, I suppose there isn't as much to talk about in exact solutions (the best one we know dates to 1962) and much more to talk about in approximations, which is where Cook has personally spent his time. That's the topic of most of this book, and includes a solid introduction to the basic concept of linear programming (a better one than I ever got in school) and some of its other applications, as well as other techniques (cutting planes, branch-and-bound, and others). The math gets a bit thick here, and Cook skips over a lot of the details to try to keep the book suitable for a general audience, so I can't say I followed all of it, but it certainly satisfied my curiosity about practical approaches to the TSP. (It also made me want to read more about linear programming.)

If you're looking for a book like this, you probably know that already, and I can reassure you that it delivers what it promises and is well-written and approachable. If you aren't already curious about a brief history of practical algorithms for one specific problem, I don't think this book is sufficiently compelling to worth seeking out anyway. This is not a general popularization of interesting algorithms (see Algorithms to Live By if you're looking for that), or (despite Cook's efforts) particularly approachable if this is your first deep look at computer algorithms. It's a niche book that delivers on its promise, but probably won't convince you the topic is interesting if you don't see the appeal.

Rating: 7 out of 10

Reviewed: 2018-10-31