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

[pyk]

http://www.math.uwaterloo.ca/tsp/star/gaia1.html

[arutar]

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.

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.

[1]: http://www.math.uwaterloo.ca/tsp/ [2]: http://www.math.uwaterloo.ca/tsp/concorde/index.html

[knuthsat → arutar]

Although here they used a Lin Kernighan Helsgaun heuristic for most of the work.

The heuristic algorithm does not use linear programming. Maybe a bit of graph theory, like minimum spanning trees or harder Steiner trees, mainly for selecting edges for the LKH heuristic.

[arutar → knuthsat]

Thanks for your comment - that is good to know. I should have looked more carefully into the article before commenting.

[nullc]

And now, finally, we can finally see why it wasn't a dimensional agreement error to assert that the Millennium Falcon made the Kessel Run in less than 12 parsecs.

Can you do the gaia run in less than 28,884,352.4 parsecs?

[DennisP → nullc]

So the Falcon isn't fast because of its engines, but because it's got a really great navigational computer.

[airstrike]

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

[saagarjha]

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 ;)

[CJefferson → saagarjha]

The gap is small, and they might close it. P not being NP doesn't mean any individual problem is hard.

A good, related problem is graph isomorphism (check if two graphs are the same, just with the vertices in a different order). The complexity of this isn't known, it's between P and NO at the moment.

However, it's VERY hard to make hard instances. Basically all real world, or randomly generated, graphs can be solved in about O(n^3) time. There is significant research into just finding the hard cases.

[sdfjkl]

Where's the missing 17,681?