Spring/Summer 1999
Volume 6, Issue 2
Spring/Summer 1998
Volume
3, Issue 1
January 1995
Volume
2, Issue 4
October 1994
Volume
2, Issue 1
January 1994
CRPC RESEARCHER SOLVES TRAVELING SALESMAN PROBLEM FOR 4461 CITIES AND ATTEMPTS TO SOLVE FOR 7397 CITIES
David Applegate, AT&T Bell Labs; Robert Bixby, Rice University; Vasek Chvatal, Rutgers University; William Cook, Bellcore
Robert Bixby of Rice University and colleagues have broken the record for the "Traveling Salesman Problem" (TSP) by finding the optimal solution to 4461 cities. Bixby worked with David Applegate (AT&T Bell Labs), Vasek Chvatal (Rutgers University), and William Cook (Bellcore), who had teamed up with him previously on the last record-setting solution of 3038 (see related article in the January 1993 Parallel Computing Research). The group is now working on a 7397-city problem. The TSP involves finding an optimal path for a salesman to take when traveling through a specified number of cities. It is typical of a large class of "hard" optimization problems that has applications in science and engineering, especially in the manufacture of circuit boards.
Table of Contents