On his book In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation
Cover Interview of February 12, 2012
In a nutshell
You wake up in the morning and find that you need to visit a number of cities or towns before returning in the evening. What is the shortest possible route to bring you to each of the locations and safely home again?
Sounds simple enough, but it is in fact a long-standing open question in mathematics—known as the traveling salesman problem, or TSP for short.
As an existential problem, any particular example of salesman routing poses no real challenge. The task comes down to determining the order in which we should visit the locations on our list. To find the best route we simply check each possible ordering and record the shortest.
So the solution for the salesman is out there, but can we actually find it?
A quick counting argument will convince you that when faced with fifty locations or so, all of the world’s computers together could not possibly check each possible ordering. The question is whether we can quickly sift through this impossibly large number of routes and pull out the shortest. Developing such an efficient solution method for the TSP is the focal point of an intense study by the research community into the nature of complexity.
In Pursuit of the Traveling Salesman traces the history of how mathematicians have slowly come to grips with the salesman problem—and how its study has led to a better understanding of the world around us. The book is aimed at a general audience, adopting the TSP to give a tour of modern applied mathematics and some of the important questions we face in the information age.
[T]he Holocaust transformed our whole way of thinking about war and heroism. War is no longer a proving ground for heroism in the same way it used to be. Instead, war now is something that we must avoid at all costs—because genocides often take place under the cover of war. We are no longer all potential soldiers (though we are that too), but we are all potential victims of the traumas war creates. This, at least, is one important development in the way Western populations envision war, even if it does not always predominate in the thinking of our political leaders.Carolyn J. Dean, Interview of February 01, 2011
The dominant premise in evolution and economics is that a person is being loyal to natural law if he or she attends to self’s interest and welfare before being concerned with the needs and demands of family or community. The public does not realize that this statement is not an established scientific principle but an ethical preference. Nonetheless, this belief has created a moral confusion among North Americans and Europeans because the evolution of our species was accompanied by the disposition to worry about kin and the collectives to which one belongs.Jerome Kagan, Interview of September 17, 2009
In a nutshell
You wake up in the morning and find that you need to visit a number of cities or towns before returning in the evening. What is the shortest possible route to bring you to each of the locations and safely home again?
Sounds simple enough, but it is in fact a long-standing open question in mathematics—known as the traveling salesman problem, or TSP for short.
As an existential problem, any particular example of salesman routing poses no real challenge. The task comes down to determining the order in which we should visit the locations on our list. To find the best route we simply check each possible ordering and record the shortest.
So the solution for the salesman is out there, but can we actually find it?
A quick counting argument will convince you that when faced with fifty locations or so, all of the world’s computers together could not possibly check each possible ordering. The question is whether we can quickly sift through this impossibly large number of routes and pull out the shortest. Developing such an efficient solution method for the TSP is the focal point of an intense study by the research community into the nature of complexity.
In Pursuit of the Traveling Salesman traces the history of how mathematicians have slowly come to grips with the salesman problem—and how its study has led to a better understanding of the world around us. The book is aimed at a general audience, adopting the TSP to give a tour of modern applied mathematics and some of the important questions we face in the information age.