See Inside

# Traveling Salesman: A Seemingly Unsolvable Problem Offers a Glimpse of the Limits of Computation

Image: Illustration by Thomas Fuchs

• ### The Best Science Writing Online 2012

Showcasing more than fifty of the most provocative, original, and significant online essays from 2011, The Best Science Writing Online 2012 will change the way...

Is it hopeless to try to compute the shortest route to visit a large number of cities? Not just a good route but the guaranteed shortest. The task is the long-standing challenge known as the traveling salesman problem, or TSP for short.

Finding a method that can quickly solve every example of the TSP would be a stunning breakthrough in mathematics. Using complexity theory, such a method would allow us to solve efficiently any computational problem for which answers can be easily verified. Most mathematicians expect this to be impossible.

But suppose that you are handed the locations of 100,000 cities. Is it really impossible to find the shortest route? We are not asking for a solution to every instance of the TSP, just the quickest way around these specific locations.

To take up the challenge, your best bet is to follow Yogi Berra’s advice: “When you come to a fork in the road, take it.” A tool called linear programming allows us to do just that by assigning fractions to roads that join pairs of cities rather than deciding immediately whether to use a road or not. In this model, it is perfectly fine to send half a salesman along both branches of the fork. The process begins with the requirement that, for every city, the fractions assigned to the arriving and departing roads each sum to 1. Then, step by step, further restrictions are added, each involving sums of fractions assigned to roads. Linear programming eventually points us to the best decision for each road and thus the shortest possible route.

I should add that 100,000 cities is not a hypothetical challenge. Current computations are zeroing in on the solution to a pretty set of 100,000 points created by Robert Bosch of Oberlin College, where the tour traces out a drawing of the Mona Lisa. We may not be able to knock off every example of the TSP, but new ideas can push the frontiers of solvability.

Here is the big picture: complexity theory suggests there are limits to the power of general computational techniques in science and elsewhere. What are these limits and how widely do they constrain our quest for knowledge? That is what research into the TSP is all about. 

This article was published in print as "The Case of the Traveling Salesman."

Already a Digital subscriber? Sign-in Now

Cook, a professor at the Georgia Institute of Technology, is author of In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation (Princeton University Press, 2012).

View
1. 1. jtdwyer 01:26 PM 5/18/12

"I should add that 100,000 cities is not a hypothetical challenge. Current computations are zeroing in on the solution to a pretty set of 100,000 points created by Robert Bosch of Oberlin College, where the tour traces out a drawing of the Mona Lisa."

A route that traces out an image of the Mona Lisa is not considered hypothetical?!?

Please come down from your lofty tower - you must be starving up there...

2. 2. LarryW 09:03 PM 5/19/12

Not a useful article. Define the problem, why it is difficult, what is complexity theory, why it is an important model for computation, why the solution of TSP could lead to solution of other problems, and how such a solution might actually cause problems (such as making computer security harder to enforce), TSP's relationship to NP complete problems.

3. 3. Will_in_BC 01:36 PM 5/21/12

I agree he article is a bit fluffy. A good explanation of NP-Complete can be found here:

http://explorations.chasrmartin.com/2008/11/24/what-are-p-np-complete-and-np-hard/

4. 4. Eco_steve 08:49 AM 6/24/12

One simple solution is to define the perimeter, then 'shrink-wrap' it until all points have been touched. The solution may not be absolutely optimal, but it is very fast.

You must sign in or register as a ScientificAmerican.com member to submit a comment.
Click one of the buttons below to register using an existing Social Account.

## More from Scientific American

• @ScientificAmerican | 12 hours ago

### Can We Harness Disruption to Improve Our World's Future?

• News | 13 hours ago

### Federal Flood Maps Left New York Unprepared for Sandy, and FEMA Knew It

• News | 15 hours ago

### Smart Wig Could Compete with Google Glass

• News | 15 hours ago | 1

### Will to Persevere Can Be Triggered by Electric Stimulation

• Climatewire | 17 hours ago | 6

More »

## Latest from SA Blog Network

• ### Wonderful Things: The Pugnacious, Alien-esque Skeleton Shrimp

The Artful Amoeba | 10 hours ago
• ### Can We Harness Disruption to Improve Our World's Future?

STAFF
@ScientificAmerican | 12 hours ago
• ### British Storm Brings Up History's First Work of Social Media

Plugged In | 13 hours ago
• ### Rolling on Wheels That Aren t Round

Observations | 13 hours ago
• ### The future of nuclear energy: Let a thousand flowers bloom

The Curious Wavefunction | 14 hours ago

## Science Jobs of the Week

Traveling Salesman: A Seemingly Unsolvable Problem Offers a Glimpse of the Limits of Computation: Scientific American Magazine

X

Give a 1 year subscription as low as \$14.99

X

X

###### Welcome, . Do you have an existing ScientificAmerican.com account?

No, I would like to create a new account with my profile information.

X

Are you sure?

X