|
Discrete Mathematics and Optimization Seminar
|
Fri, Mar. 12th, 2010 10:35 AM, Trottier Building 2100
In Pursuit of the Salesman: Mathematics at the Limits of Computation
Bill Cook
Georgia Tech
|
The traveling salesman problem, or TSP for short, is easy to state: given
a number of cities along with the cost of travel between each pair of them,
find the cheapest way to visit them all and return to your starting
point. Easy to state, but difficult to solve! Despite decades of research
by top applied mathematicians around the world, in general it is not known
how to significantly improve upon simple brute-force checking. It is a real
possibility that there may never exist an efficient method that is guaranteed
to solve every instance of the problem. This is a deep mathematical question: Is there an efficient solution method or not? The topic goes to the core of
complexity theory concerning the limits of feasible computation. For the
stout-hearted who would like to tackle the general version of the TSP,
the Clay Mathematics Institute will hand over a $1,000,000 prize to anyone
who can either produce an efficient general method or prove an impossibility
result.
The complexity question that is the subject of the Clay Prize is the Holy Grail
of traveling-salesman-problem research and we may be far from seeing its
resolution. This is not to say that mathematicians have thus far come away
empty-handed. Within the theoretical community the problem has led to a large
number of results and conjectures that are both beautiful and deep.
In the arena of exact computation, an 85,900-city challenge problem was solved
in 2006, in a computation that took the equivalent of 136 years on
top-of-the-line computer workstations. On the practical side, solution
methods are used to compute optimal or near-optimal tours for a host of
applied problems on a daily basis, from genome sequencing to arranging
music on iPods.
In this talk we discuss the history, applications, and computation of
the TSP, together with an open research area connecting planar
graphs and the linear-programming approach to the problem.
|
|
|
|