Approximating the Travelling Salesperson Problem

The bad news:  There cannot be a polynomial-time RHO-approximation algorithm for the TSP, for any value of RHO >= 1, unless P = NP.  We will return to this later, and prove it.

The good news:  If we impose a very reasonable restriction on the edge weights of the graph, we can actually get quite a good approximation algorithm for the TSP.

The Triangle Inequality:  In a triangle drawn in a plane, the length of each edge is less than or equal to the sum of the lengths of the other two edges.  

If  we require that our graph satisfies the Triangle Inequality (regardless of whether the edges are straight or curved or can actually form valid triangles in normal space), it turns out that this is sufficient to ensure that we can find a good approximation to the optimal solution to the TSP.

The first step in developing our approximation algorithm is to find something in the graph that will give us a lower bound on the cost of the optimal solution C* for the TSP problem.  The second step will be to use the structure from which we derived the lower bound to build a solution which is still relatively close to C* in cost.

Consider an optimal solution to the TSP problem (in a graph where the edge-weights satisfy the Triangle Inequality).  Let C* be the cost of the optimal solution.  The optimal solution forms a Hamiltonian Cycle - if we delete any edge of it, we are left with a Hamiltonian Path ... and a Hamiltonian Path is a spanning tree of the graph.  Let T be a Minimum Spanning Tree of the graph.  Let W(T) be the weight of T.  By definition, W(T) <= the weight of the Hamiltonian Path, which is < the weight of the optimal solution.

Now consider a walk that traverses T.  This walk is effectively the result of starting at any vertex and exploring T in a depth-first manner.  This walk is not a Hamiltonian Cycle (it uses every edge twice, and potentially visits any vertices more than once) but it is getting closer.  Since this walk includes every edge of T exactly twice, the weight of the walk is exactly twice the weight of T.

We now simplify the walk by eliminating repeated visits to vertices.  Suppose the walk visits three vertices in this sequence: a-b-c, and suppose that this is not the first visit to vertex b.  We simply eliminate this visit to b from the walk: we replace the steps from a to b and from b to c by the single step from a to c.  The key observation is that due to the triangle inequality, this replacement cannot increase the total weight.

Repeating this simplification process will eventually lead to a Hamiltonian Cycle, which is after all just a walk that includes every vertex once and returns to its start.  Let the weight of this cycle be C.  Since the weight never increases, C <= 2W(T), and as we know W(T) < C*, we can combine these to get
                                C < 2C*

Thus the algorithm described is a 2-approximation algorithm for TSP with Triangle Inequality.