The Traveling Salesman Meets A Computer Scientist

October 11, 2000
12:30 pm - 1:30 pm
Halligan 111
Speaker: Vasek Chvátal, Rutgers University


David Applegate, Bob Bixby, Bill Cook, and I have written a computer code, available at 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.