{nytimes/ Mar. 14, 2012 /'interactive'}
 
Willy Loman, the tragic hero in the current Broadway revival of “Death of a Salesman,” may think he has problems. But it turns out he’s got nothing on the hypothetical road warriors in William J. Cook’s new book, “In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation,” who are pushed to visit hundreds, thousands, even millions of different cities, mostly in pursuit of someone else’s mathematical glory.
 
Mr. Cook, a professor of industrial and systems engineering at the Georgia Institute of Technology, offers a cheerful biography of the Traveling Salesman Problem, which was born as a major mathematical preoccupation in the late 1940s, around the same time as Loman himself, but has gone on to have a far more satisfying career.
 
Today, the problem — which essentially involves finding the most efficient route between a list of geographical points — is a key concept in applied efficiency research and is used to direct telescopes, manufacture customized computer chips, route school buses, map genomes, speed up video games, and even, Mr. Cook notes, “minimize wallpaper waste.”
 
In Arthur Miller’s play Loman’s route between New York and New England is punishing enough that early in the drama he mulls a transfer. A firmer grip on the Traveling Salesman Problem might have saved him at least some of his exhaustion.
 
Not that the technology available at the time would have necessarily been enough to solve it. As Mr. Cook explains, tackling even a modest version of this puzzle simply by measuring and adding up each leg requires staggering numbers of calculations, even by the standards of today’s computers.
 
.. Mapping out an optimized route for a 33-city version of the problem used in a 1962 contest sponsored by Procter & Gamble, Mr. Cook notes, involves measuring 131,565,418,466,846,765,083,609,006,080,000,000 possible routes, which would take the Department of Energy’s $133 million Roadrunner supercomputer roughly 28 trillion years. {Note that the universe itself is only 14 billion years old}.
 
.. As a result, the real challenge in solving the Traveling Salesman Problem has to do with finding mathematical shortcuts that allow one to determine the most efficient route without simply measuring each one.
 
In his book, Mr. Cook offers plenty of history to go with his math, starting with the 18th-century mathematicians who pondered efficient river crossings in Germany and the more practical problems of Abraham Lincoln, who as a circuit-riding lawyer in the 1850s had to travel among 14 different Illinois courthouses.
 
The Traveling Salesman Problem was described in the early 19th century, but it was a problem without a name until 1949, when the mathematician Julia Robinson first used the term in a paper .. {that’s the same year Miller’s play opened}.
 
Procter & Gamble’s 33-city contest, presented as a way of helping Officers Toody and Muldoon from the television show “Car 54, Where Are You?” went unsolved in 1962. But in 1971, a team from 'IBM' solved it for 64 cities, and mathematicians have been pushing the salesman farther and farther ever since.
 
Today’s record, set in 2006, maps the location of 85,900 connections on a customized computer chip. But even after decades of hard solving, there’s still plenty of new territory to conquer. Mr. Cook and some colleagues have put together a {still unsolved} 1,904,711-point World Traveling Salesman Problem, which takes in every city, town and village in the world, plus a few Antarctic research stations.
 
Meanwhile, the Clay Mathematics Institute is offering a $1 million prize to anyone who can show whether the Traveling Salesman Problem can be fully solved at all, which the mathematician Jordan Ellenberg recently called “the biggest open problem in complexity theory.”
 
It’s still not clear if that ultimate solution would bring on a global apocalypse {as happens in Charles Stross’s 2001 science-fiction short story “Antibodies”} or usher in an age of unparalleled abundance, allowing optimization of resources that “would make the whole Internet look like a footnote in history,” as the computer scientist Lance Fortnow has argued.
 
Mr. Cook thinks the problem may not be fully solvable at all. Leaving the hypothetical Willy Lomans' wandering indefinitely. “The salesman may defeat us in the end,” Mr. Cook writes, “but not without a good fight.”