Finding most effective upper bound for TSP using MST

Question

I'm curious as to what the most effective methods are to find the most optimal (or close to optimal) upper bound for the TSP using a MST. I'm trying to optimize my algorithms for speed, but I'm having trouble algorithmically computing "good" bounds after I find the MST. I know a base bound would be 2 x MST length, but this doesn't seem to be the best we can do. Any references or insight would be appreciated.

Answer 1

You should probably convert the MST into a tour, and that'll give you a bound less than 2 * MST length, in linear time. There is also an extension to MST, called Christofide's Algorithm that might be worth looking into as well.

Recommend taking a look at the Wikipedia page for TSP heuristics.