Other Algorithms

Other approximation algorithms have been proposed.

• One starts with an MST and then uses a matching algorithm to add some edges to the tree from which we can build a good tour. Ratio is 3/2 and good tours are found in practice.
• For TSP in 2-d, there is a dynamic-programming algorithm that exploits the sequence structure of the tour to find approximations with arbitrarily good ratios (the ratio shows up in the exponent in the running time).