[Fall 1998
Colloquiums]
[Department Homepage]
DEPARTMENT OF MATHEMATICS AND STATISTICS
OAKLAND UNIVERSITY
ROCHESTER, MICHIGAN 48309
William J. Cook, Noah Harding Professor
Department of Computational and Applied Mathematics
Rice University
On the Solution of Traveling Salesman Problems
Abstract
Following the theoretical studies of J.B. Robinson and H.W. Kuhn in the late 1940s and the early 1950s, G.B. Dantzig, R. Fulkerson, and S.M. Johnson demonstrated in 1954 that large instances of the TSP could be solved by linear programming. Their approach remains the only known tool for solving TSP instances with more than several hundred cities; over the years, it has evolved further through the work of M. Grötschel, S. Hong, M. Jünger, P. Miliotis, D. Naddef, M. Padberg, W.R. Pulleyblank, G. Reinelt, G. Rinaldi, and others. We discuss some of its refinements that led to the solution of a 13,509-city instance. This talk is based on joint work with D. Applegate, R. Bixby, and V. Chvátal.
372 Science and Engineering Building
Tuesday, October 27, 1998
3:004:00 P.M.
Refreshments at 2:303:00 P.M. in Room 368, Science and Engineering Building