On his book In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation

Cover Interview of February 13, 2012

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.

Spontaneous generation is one of those wrong theories that clutter the basements of the biological sciences and that now look so very obviously wrong that it is hard to see how anyone could have taken them seriously in the first place. Why wouldn’t it occur to anyone that flies might be laying eggs that were too small for us to see? How simple would the crucial experiment be? What I have tried to do in much of my work is to turn this ‘obvious wrongness’ on its head—why, exactly, does it seem so obviously wrong?—and see what the new picture that emerges from that inquiry says about science and our belief in its results.

It’s commonplace to say that humor is subjective, since what’s funny to you might not be funny to me. But humor is also a loaded concept. If you – or your people – have no sense of humor, or the wrong one, that means you’re less rational, tolerant, understanding, or civilized. You don’t get it. Or, worse, you lack something human. Modern Chinese debates about humor were very much caught up with these fundamental questions of value.

## 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 SalesmanandTraveling 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.