Review: In Pursuit of the Traveling Salesman, by William J. Cook

[Russ Allbery]

In Pursuit of the Traveling Salesman
by William J. Cook

Publisher: Princeton University
Copyright: 2012
ISBN:      0-691-15270-5
Format:    Kindle
Pages:     272

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

-- 
Russ Allbery (eagle at eyrie.org)              <http://www.eyrie.org/~eagle/>