William J. Cook

William Cook is the Chandler Family Chair and Professor at Georgia Tech. He is a member of the National Academy of Engineering and a fellow of the Society for Industrial and Applied Mathematics and of the Institute for Operations Research and Management Sciences.

In Pursuit of the Traveling Salesman - A close-up

In the hands of your browsing reader, I'd like the book to fall open to a pair of pages displaying two paintings by Julian Lethbridge, Traveling Salesman and Traveling Salesman 4. These are not pieces of mathematics, but they capture well the beauty of the salesman problem that attracts so many mathematicians to its study.A traveler concerned about mileage will not cross her own path during a tour. Thus a shortest tour can be drawn as a line that loops around but never crosses itself. Such a line, known as a Jordan curve, divides space into two regions, an inside and an outside. Think of a fence running around the boundary of a park or think of the coastline of an island.The first of Lethbridge's paintings shows vividly the division of space created by a good solution to the salesman problem. Lethbridge uses colors and textures to highlight the interior and exterior, separated by a rendering of the tour itself. The division of space feels natural, suggesting that short tours are, in a sense, organic objects.The second painting displays the same tour as the first, but highlights the complexity of discovering the partition of space inherent in the locations of the points to be visited. Lethbridge uses multiple colored strokes emanating from each turn of the salesman tour. Following the strokes from point to point, one quickly gets lost in the myriad of alternative paths.In Pursuit of the Traveling Salesman aims to spread the word that mathematics is alive and well.In the TSP we have a simply stated problem that nonetheless gets to the heart of modern complexity issues and has important applications in numerous settings. The fact that future progress, and perhaps a million-dollar prize, may lie at the tip of the reader's pencil can hopefully serve to capture the attention and imagination of young and old alike.If I can attract a few people to join the next generation of applied mathematicians, then the book will have been a success.

Editor: Erind Pajo
February 13, 2012

William J. Cook In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation Princeton University Press272 pages, 6 x 9 inches ISBN 978 0 691 15270 7

Support this awesome media project

We don't have paywalls. We don't sell your data. Please help to keep this running!