The Traveling Salesman Meets A Computer Scientist
October 11, 2000
12:30 pm - 1:30 pm
Halligan 111
Speaker: Vasek Chvátal, Rutgers University
Host: Dr. D. Souvaine
Abstract
David Applegate, Bob Bixby, Bill Cook, and I have written a computer code, available at http://www.keck.caam.rice.edu/concorde.html for solving instances of the traveling salesman problem and used in 1998 to solve a geographical instance with 13,509 cities. One part of the code consists of cutting-plane heuristics inspired by data structures from computer science such as the minimum prefix trees and PQ-trees. This is the part that I will talk about.