Tutte Colloquium - Bill Cook

Friday, March 12, 2021 3:30 pm - 3:30 pm EST (GMT -05:00)

Title: An approximate solution to a 2,079,471-point traveling salesman problem

Speaker: Bill Cook
Affliation: University of Waterloo
Zoom: Please email Emma Watson


Together with Keld Helsguan, we have found a TSP tour through the 3D positions of 2,079,471 stars. We discuss how linear programming allows us to prove the tour is at most a factor of 0.0000074 longer than an optimal solution. The talk will focus on the use of minimum cuts and GF(2) linear systems, to drive the cutting-plane method towards strong LP relaxations.