Title: The traveling salesman problem with road distances

NOTE: This seminar will not be recorded by request of the speaker

Abstract: Following Dantzig, Fulkerson, and Johnson, we show that a certain tour of 49,603 sites in the US is shortest possible, measuring distance with point-to-point routes obtained from Google Maps. We highlight a cost-refinement technique that allows the cutting-plane method to generate lower bounds on the tour length without explicit knowledge of the full distance matrix. The talk is based on joint work with Daniel Espinoza, Marcos Goycoolea, and Keld Helsgaun.