À¶Ý®ÊÓƵ

°Õ¾±³Ù±ô±ð:ÌýAn approximate solution to a 2,079,471-point traveling salesman problem

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.