Galaxy TSP
MIT, Cornell University, Columbia University
MIT, Cornell University, Columbia University
NeurIPS Workshop on Learning Meets Combinatorial Algorithms, 2020
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.
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.