How do you approximate the traveling salesman problem?

Answer 1

Given an un-directed fully connected graph (there is an edge between every two vertices) with a weight function that has the triangle inequality. I.e., if (u,v), (v,w), (u,w) in E then w(u,v) + w(v,w) >= w(u,w). Do:

• find a minimum spanning tree
• split each edge in the tree into two edges. Since all the degrees in the new graph are even, there is an Euler cycle in the graph. Find it.
• Whenever you can, cut corners. I.e., if the Euler path goes: v --> u --> v --> w, change it to go: v --> u --> w. From the assumptions on the graph we can only gain from this and we are guaranteed that there an edge u --> w.

Ratio from the optimum:

Note that the optimum (opt) path costs at most the value of the MST (just take one edge off the opt and you get a spanning tree). Since our path is at most twice the cost of the spanning tree we have a ratio of x2.