TSP Tour in 3D through 2,079,471 stars (opens in new tab)

(math.uwaterloo.ca)

44 pointspyk5y ago9 comments

9 comments

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

knuthsat5y ago

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.

arutar5y ago

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

nullc5y ago

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?

DennisP5y ago

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

airstrike5y ago

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

saagarjha5y ago

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

CJefferson5y ago

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.

sdfjkl5y ago

Where's the missing 17,681?

j / k navigate · click thread line to collapse

9 comments

arutar5y ago

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

knuthsat5y ago

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.

arutar5y ago

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

nullc5y ago

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?

DennisP5y ago

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

airstrike5y ago

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

saagarjha5y ago

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

CJefferson5y ago

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.

sdfjkl5y ago

Where's the missing 17,681?

j / k navigate · click thread line to collapse