Galaxy TSP

Iddo Drori, Brandon Kates, William R. Sickinger, Anant Kharkar, Brenda Dietrich, Avi Shporer, Madeleine Udell

MIT, Cornell University, Columbia University

NeurIPS Workshop on Learning Meets Combinatorial Algorithms, 2020

We approximate a Traveling Salesman Problem (TSP) three orders of magnitude larger than the largest known benchmark, increasing the number of nodes from millions to billions. Previously, the World TSP dataset served as the largest benchmark for TSP approximation with 1.9 million cities. The dataset we use is currently the largest catalog of stars in the Milky Way, which we call Galaxy TSP, consisting of 1.69 billion stars. We use a divide and conquer approach for approximating the TSP by splitting the problem into tiles, approximating each tile, and merging the approximations. We learn how to split tiles for efficient computation. We demonstrate our approach on the optimization of space telescope target scheduling.