« search calendars« DIMACS Workshop on Computational Approaches to Vehicle Routing with a Tribute to David S. Johnson
« Computing Tours and Lower Bounds for Very Large Instances of the Traveling Salesman Problem
Computing Tours and Lower Bounds for Very Large Instances of the Traveling Salesman Problem
May 23, 2023, 4:10 PM - 4:50 PM
Location:
DIMACS Center
Rutgers University
CoRE Building
96 Frelinghuysen Road
Piscataway, NJ 08854
Click here for map.
Bill Cook, University of Waterloo
Together with David Applegate and Keld Helsgaun, we have found a tour through the 3D positions of 265,637,087 stars. We discuss how linear programming allows us to prove the tour is at most a factor of 1.00025 longer than an optimal tour. Like most computational studies, our work has been influenced by ideas of David Johnson. We discuss his great TSP research, focusing on an experimental estimate of the BHH constant.
[Video]