William Cook (University of Waterloo): An approximate solution to a 2,079,471-point traveling salesman problem

EGERVÁRY SZEMINÁRIUM

Abstract: 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 GF(2) linear systems to drive the cutting-plane method towards
improved LP relaxations of the TSP.