TSP Tour in 3D through 2,079,471 stars

I had the privilege to take a linear programming course with Bill, back when he still taught at the University of Waterloo. He spent some time discussing the TSP. TSP solving methods are very interesting, and the techniques used here essentially boil down to setting up an appropriate linear program (albeit with a large number of constraints relative to the number of nodes) and then using duality to obtain accuracy certificates.<p>The research group maintains an excellent webpage with many resources about the TSP [1]. They have also developed an app (Concorde TSP) [2] which provides really good graphical representation of the algorithm. There is an iOS app as well under the same name which has a nice interface.<p>[1]: <a href="http:&#x2F;&#x2F;www.math.uwaterloo.ca&#x2F;tsp&#x2F;" rel="nofollow">http:&#x2F;&#x2F;www.math.uwaterloo.ca&#x2F;tsp&#x2F;</a> [2]: <a href="http:&#x2F;&#x2F;www.math.uwaterloo.ca&#x2F;tsp&#x2F;concorde&#x2F;index.html" rel="nofollow">http:&#x2F;&#x2F;www.math.uwaterloo.ca&#x2F;tsp&#x2F;concorde&#x2F;index.html</a>

And now, finally, we can finally see why it wasn&#x27;t a dimensional agreement error to assert that the Millennium Falcon made the Kessel Run in less than 12 parsecs.<p>Can you do the gaia run in less than 28,884,352.4 parsecs?

Right click and hold on the image to the right if you want to hear your CPU fan spin

To be clear, this is a TSP approximation that has been shown to be fairly close to the theoretical optimum. P has not yet been shown to equal NP ;)

Where&#x27;s the missing 17,681?