Easy money. Maybe.
Our tour through 2,079,471 stars has length 28,884,352.4 parsecs, measured to the nearest 1/10th parsec along each star-to-star leg. We don't know if this is a shortest-possible route. But we know it's close. Using linear programming, we have proven no tour can have length less than 28,884,137.8 parsecs. The route we have is at most 213.4 parsecs too long, less than a factor of 0.0000074 of its total length. Close, but maybe not perfect.
Both the construction of the tour and the proof of its quality guarantee are the result of a stack of mathematics and long and difficult computations. The goal of the work is to discover new techniques in mathematical optimization. For this, it would be great to know where we really stand in the attempt to solve perfectly this large instance of the TSP. Maybe you can help! And pick up spare cash along the way. I'm offering $50 for each parsec you can shave off the tour. Find a route that is 200 parsecs shorter and grab $10,000.
A precise description of gaia2079471 can be found on the data page. If you plan to tackle the problem, play close attention to the use of the TSPLIB distance norm, described in the "Computing Distances" section of the data page -- the TSPLIB distance between two points is the straight-line (square-root) distance rounded to the nearest integer value. A good way to test your implementation of the distance function is to check that the route given on the tour page evaluates to exactly 288843524.
To collect your money, find a tour that evaluates to less than the best length posted on this page, currently 288843524. When you have such a tour, send it to bico@uwaterloo.ca as a text file containing a permutation of the integers 1 up to 2,079,471, with one integer per line, along with permission to post the tour and its length on this page. We will check its length, post the results (citing you), and contact you about sending/transferring the money. The reward is $5 for each (1/10th parsec) unit your tour saves over the current best result.
I'm capping the total payments to $10,000, to be sure there are enough funds to pay you right away. As I mentioned earlier, Keld and I won $17,000 in the Traveling Santa Kaggle competition last year. Some of it is sitting in the bank, waiting to be sent to you.
When searching for an improved tour, you can start from scratch (it would be really cool if you found a better tour in this way) or start from the current best tour and hunt for a short cut. Good luck!