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 |
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 minimum cuts and GF(2) linear systems, to drive the cutting-plane method towards strong LP relaxations.