Joint Penn-UDel Colloquium on the Nature of Computing
The Traveling Salesman Problem With Priority Constraints
Neil Simonetti
We consider certain restricted traveling salesman problems. Some important real-world problems are special cases of this model or some of its close relatives.
We discuss an implementation of a dynamic programming algorithm for the general case when the integer k is replaced with city-specific integers. One important feature of our implementation is that we construct in advance, without knowledge of any particular problem instance, a typical layer of an auxiliary supernetwork that can be stored and subsequently used to solve any instance up to a specific limit on k. This advance construction, which needs to be done only once, absorbs the bulk of the computing time.
Our algorithm, when applied to N cities, requires O(k*k 2^k N) time steps, and O(k 2^k) memory. When using conventional workstations, the time complexity is usually not as limiting as the memory requirement.
(This is joint work with Egon Balas of Carnegie Mellon University.)
Thursday, May 21, at 3 pm
in Room 207 of the
Johnson Pavilion
(see map)
near Spruce and 36th Streets on the
University of Pennsylvania campus.
Travel Directions are found at
http://www.upenn.edu/fm/map/dir.html