Book review: In Pursuit of the Traveling Salesman

As mathematical problems go, the “traveling salesman problem” (TSP) is a rare gem: it is simultaneously of great theoretical, historical, and practical interest. On the theoretical front, it is a well-known example of the class of “NP-complete” problems, which lie at the heart of the million-dollar “P vs NP” question (which I still intend to explain at some point). Historically, it has been studied for almost 200 years (given a sufficiently inclusive definition of “study”), and has occupied a place in the public consciousness for at least the last 50. And this great historical interest is partly due to the problem’s practical significance.

So, what is it? Given a set of points in the plane (or, more generally, a set of points with “distances” specified somehow between each pair of points), the problem is to determine the shortest path which visits every point exactly once and then returns to the starting location. Of course, in one sense this is “easy”: just list all possible paths and compute the length of each. Note, however, that for a set of n points, there are (n-1)! (that is, 1 \cdot 2 \cdot 3 \cdot \dots \cdot (n-1)) possible paths that visit every point once and then return to the start. Even with only 30 points, that’s a whopping 8841761993739701954543616000000 possible paths—if you could compute the length of one trillion paths every second, it would still take 280 million millenia (that’s 2.8 \times 10^{11} years, slightly longer than I’ve been alive) to check all of them! And that’s only 30 points—in practice, people want to solve the TSP for sets of points much larger than 30. So the point is not just to “solve” the problem; the real question is, can it be solved efficiently?

Amazingly, no one knows! But that hasn’t stopped people from coming up with extremely clever algorithms that seem to work well in practice, on very large sets of points (i.e. thousands, or even tens of thousands of points)—even though there are “pathological” inputs for which these algorithms do essentially no better than just trying every path. So these algorithms constitute a good solution to the TSP from a practical point of view but not a theoretical one!

William Cook’s new book, In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation, does a wonderful job presenting the history and significance of the TSP and an overview of cutting-edge research. It’s a beautiful, visually rich book, full of color photographs and diagrams that enliven both the narrative and mathematical presentation. And it includes a wealth of information (perhaps even a bit too much at times; I got lost in a few places). But it actually bills itself, partly, as an introduction to cutting-edge ideas in TSP research—and I think overall it succeeds admirably, explaining ideas in ways that are accessible but not patronizing. Read this book if you want a fun, beautifully illustrated introduction to (this one fascinating piece of) the edge of human knowledge!

About these ads
This entry was posted in books, computation, geometry, open problems, review and tagged , , . Bookmark the permalink.

6 Responses to Book review: In Pursuit of the Traveling Salesman

  1. Josh says:

    How much detail, if any, does the book describe approximation techniques for solving TSPs?

    If you haven’t already read it, I think you would really like Turing’s Cathedral by George Dyson. Also, since I’m a Philadelphia native myself and current Drexel grad student, I recommend you check out the Turing Centennial Celebration at Princeton University coming up (https://www.princeton.edu/turing/ ).

    Another book I just read which you would like (again, I’d be surprised if you haven’t already read it): Fermat’s Enigma.

    BTW, I can’t believe wordpress supports inline \LaTeX! I don’t know how I missed this\dots

    • Brent says:

      There is a bit on approximation techniques in Chapter 4, but I have no idea how much detail it includes relative to how much there is that could be said.

      Thanks for the recommendations! I hadn’t heard of Turing’s Cathedral, and while I have heard of Fermat’s Enigma I actually haven’t read it (!). I am, however, already registered for the Turing Centennial Celebration!

      For latex you have to add the word ‘latex’ after the opening dollar sign, like $ latex \pi$ (but without the space) which generates \pi. Also, capitalization of the \LaTeX command matters. =)

      • Josh says:

        Ah… thanks for the correction. And I can’t believe I made a rookie mistake like forgetting the capitalization in \LateX. If only I could compile my posts before posting… BTW, perhaps you know another PhD at Penn, Daniel W.? My wife was roommates with his sister at college.

        • Brent says:

          Hah, small world! Daniel W. is a good friend of mine, we’re in the same research group.

          We should meet up for coffee or lunch or something sometime. If you’ll be at Bob Sedgewick’s talk on Monday we could try to meet there.

          • Josh says:

            If only… I’m in Georgia until until August. But once I return to Philadelphia, and if you guys haven’t move on by then, I’ll take you up on your offer.

            • Brent says:

              Ah, OK. Yeah, we’ll probably be in Philly for another couple years. I’ll look forward to meeting you next fall then!

Comments are closed.