Puzzles for Programmers and Pros

6.9. Revisiting a Traveling Salesman

The Traveling Salesman Problem, affectionately known as TSP, lies at the heart of many problems, including optimizing the deliveries of trucks, scheduling tour stops, and laying out wires. TSP yields very nicely to heuristics, but it also admits some beautiful theory.

A certain salesman, we'll call him Bob, starts at a certain city C and wants to visit a certain set of other cities by car at least once and then return to C. (Factoid: What is the preferred profile of salespeople from pharmaceutical companies who call on doctors? Answer: Former cheerleaders.) Travel times and costs may vary, but we will assume that the costs are positive, symmetric, and that the triangle inequality holds. Symmetry means that going from X to Y costs the same as going from Y to X. The triangle inequality means that going from X to Y to Z cannot be cheaper than going directly from X to Z (it could be the same price, but not cheaper).

The question is whether Bob can visit all his cities for a certain price or less. As you can see, if someone proposes a solution, you can verify that it meets the price budget easily, but finding a solution below a certain price can be hard—it may require exploring all possible paths.

Many people hear this problem and think: "Why can't a greedy approach work? That is, from each city, I'll just go to the next nearest one."

How bad can ...