Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

The traveling salesman problem 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, 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 and we may be far from seeing its resolution. This is not to say, however, that the research community has thus far come away empty-handed. Indeed, the problem has led to a large number of results and conjectures that are both beautiful and deep, and 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 salesman problem.

Bio: Professor Cook's research interests are in combinatorial optimization and integer programming. He is also heavily involved in research dealing with computational issues involved in treating hard discrete problems such as large instances for the celebrated traveling salesman problem.

Honors & Awards: National Academy of Engineering 2011; Fellow, INFORMS 2010; Fellow, Society for Industrial and Applied Mathematics (SIAM) 2009; Lanchester Prize, INFORMS 2007; I.E. Block Community Lecturer prize, SIAM (the Society for Industrial and Applied Mathematics) 2003; Beale-Orchard-Hays Prize for Excellence in Computational Mathematical Programming 2000; International Congress of Mathematicians (ICM) Semi-plenary talk 1998; International Symposium on Mathematical Programming (ISMP) Plenary talk 1994, 2003