William J. Cook
In Pursuit of the Traveling Salesman
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
In Pursuit of the Traveling Salesman
William J. Cook In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation Princeton University Press 272 pages, 6 x 9 inches ISBN 978 0 691 15270 7
Available here →February 13, 2012
20120213-cook-william-on-in-pursuit-of-traveling-salesman-3-1
A close-up
The rest of this thread
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.
Pull this thread
pulls againstpulls alongside
Salesman routing is no toy problem, an efficient algorithm for it would solve genetic sequencing and processor design too.
Against BC · No natural line divides pure from adulterated food, and between the 1860s and 1906 the line moved into the laboratory. On: Mathematical objects and disciplinary categories are discovered rather than made
Against SB · Property has no true nature. On: Mathematical objects and disciplinary categories are discovered rather than made
Against CG · Meibutsu is one interlinked system of named, famous and regional things, rooted in elite connoisseurship rather than regional food. On: Mathematical objects and disciplinary categories are discovered rather than made
Alongside DH · Atoms decay at unalterable rates and carry no memory, so they are better historians than any human record. On: Mathematical objects and disciplinary categories are discovered rather than made
Alongside TV · A single process, combogenesis, generates everything in the universe in exactly twelve levels from quarks to geopolitical states. On: Mathematical objects and disciplinary categories are discovered rather than made
Alongside JB · Energy's worth depends on its entropy, so a kilowatt hour of electricity and one of gas are different goods. On: Mathematical objects and disciplinary categories are discovered rather than made
Nearby KA · The lie detector has survived eighty years of scientific refutation because it was never science.
Nearby TP · Human heredity became a science inside insane asylums, and eugenic ambition was in it from the start.
Know something the rest of us don't?
Most threads on Rorotoko begin with our invitation. Any thread can begin with a proposal: you write it with the same prompts every thread answers, and we read it.
Propose a thread →