 |
 |
 |
 |
 |
 |
 |
 |
2:00 PM-3:00 PM
Chair: William H. Cunningham, University of Waterloo, Canada
Room: Earth Science Center Auditorium
In 1954, Dantzig, Fulkerson, and Johnson demonstrated that large instances of the TSP could be solved via linear programming duality. Their approach remains the only method known for solving TSP's having more than several hundred cities. The speaker will discuss the evolution of their methodology, including work of Grötschel, Hong, Padberg and others. He will also demonstrate a technique for using optimal solutions to tiny TSP instances in order to improve the linear programming bounds for large instances. Finally, he will discuss the most recent computational advances on the TSP. This presentation is based on joint work with David Applegate, Robert Bixby, and Vasek Chvátal.
William Cook
Computational and Applied Mathematics
Rice University
|
|
|
|
|
|
|
|