Slice of StarHorse 1 Tour

136,606,128 Stars

StarHorse 1

The full StarHorse catalogue contains 3D positions for 265,637,087 stars, providing a beautiful example of the traveling salesman problem. But the StarHorse authors note they can raise the overall quality of the collection by filtering out certain entries that may be problematic.

"After cleaning our results for both unreliable input and output data, we retain 137 million stars, for which we achieve a median precision of 5% in distance ..."

The surviving set of 136,606,128 stars is still plenty large for a TSP challenge, and a good stepping stone towards the StarHorse and Gaia DR2 instances. Details of the point set can be found on the data page.

As of October 6, 2020, our best tour for this example has length 1,417,590,536.2 parsecs. We expect to have a good lower bound on the tour length in another month or two, when we bring online software that can handle the huge linear-programming models that need to be solved.

Research team

  • David Applegate, Google Research
  • William Cook, University of Waterloo and Johns Hopkins University
  • Keld Helsgaun, Roskilde University


Links to lots of information on the mathematical techniques we have employed can be found on the TSP home page and on the LKH web site.

Details on the point set for the star TSP instance are given on the Data page; images can be found on the Tour page.

Computations were carried out on systems located at Google Research, Roskilde University, and the University of Waterloo. We thank our institutions for their support.