Finding a very-close-to-optimal tour through 2,079,471 stars

Professors Bill Cook (C&O) and Keld Helsgaun (Roskilde University, Denmark) have found a Hamiltonian tour through the three-dimensional positions of over two million stars, as obtained from the European Space Agency's Gaia Data Release 1. The total length of the tour is 94,208,157.5 light years and, most remarkably, has been proven to be within a factor of 0.0000074 of the shortest possible tour. Bill and Keld write that "it's like a New York to Los Angles road trip guaranteed to be within half a city block of the optimal cross-country drive."

The tour was found using an array of heuristic-search techniques for solving the Traveling Salesman problem (TSP). The quality guarantee was obtained by a linear programming, cutting-plane method. More details can be found here. 

Bill and Keld's work has been featured in New Scientist magazine.