Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

Is there an explanation Christofides's Heuristic for solving TSP which does not simply state the algorithm and go ahead to prove the bound?

To be specific: (Disclaimer : I am an engineer who knows very little about graph theory but need this for a logistics course)

  • I understand that I first create an MST. So far, so good.
  • Now, I need to find a perfect minimum weight matching on all odd degree nodes. I have no clue what this is; googling this tells me this is a set of edges containing maximum $n/2$ edges such that no node is shared by 2 sets. I don't see why I am doing this..... I am not even sure I understand what this statement means.
  • Now, I need to merge the MST and the matchings to create a "multigraph" and then find an Eulerian tour on this. No clue what I am doing here.
  • Run the shortcut algorithm exploiting the triangle inequality. (No clue what happened till now and this obviously then makes no sense either)

Can someone point me to a good resource with possible examples and illustrations for why Christofides works in a language that isn't full of graph theory terms (or alternately, provide me an answer here)?

I have already looked at :

share|improve this question
add comment

1 Answer

up vote 5 down vote accepted

In the long run, it's really better to understand the graph theory terminology, but for now, here is an explanation of Christofides's algorithm. I'm not an expert in this area so I can't offer much by way of intuition. Also, I should note that by now, better algorithms are known for some variants, see for example the recent survey by Vygen.

We denote the sum of costs of a tour or of similar objects by $w(\cdot)$. Fix some optimal TSP tour $H$.

The starting point of the algorithm is a minimum spanning tree $T$. Why do we want a minimum spanning tree? Suppose that instead of a TSP tour, we're interested in a TSP path. A TSP path is a spanning tree, and while it is difficult to find an optimal TSP path, it's easy to find a minimal spanning tree. In the case of a TSP tour, we have $w(T) \leq w(H)$ as well.

If $T$ happens to be a path then, with some luck, we can get a good tour by completing it into a cycle. However, this need not be the case, and $T$ can be a complicated tree. Here we use a trick: Euler proved that every graph with even degrees can be traversed by an Eulerian circuit. While we wanted a tour and not just any circuit, this happens not to matter as we will see below.

How do we make $T$ into a graph with even degrees? The obstructions are the vertices with odd degree, so we'd like to pair them (there must be an even number of them since the sum of degrees in a graph is always even) as cheaply as possible. This is the minimum-weight matching you mentioned. We complete $T$ into an even-degree graph $T'$ by adding a matching $M$ on the odd-degree vertices, which is just a set of edges connecting pairs of odd-degree vertices. For obvious reasons, we want $M$ to have as minimal weight as possible, and such a matching can be found effectively. (As a special case, if $T$ is a path then $M$ connectes its two endpoints, and $T'$ is just a cycle.)

All vertices in $T'$ have even degree, so we can find an Eulerian tour $E$ working its way over all edges of $T'$. However, we wanted a Hamilton cycle (another name for a TSP tour). The idea now is to follow the Eulerian tour. Whenever we're supposed to visit a vertex we have already encountered, we just "skip" this edge. Eventually the tour will reach a new vertex, and then we just connect the previous vertex with the new one. The triangle inequality shows that the resulting TSP tour has weight at most $w(T') = w(T) + w(M)$.

Here is an example: suppose the Eulerian tour starts $a,b,c,a,d$. The constructed TSP tour will start $a,b,c,d$. The cost of the Eulerian tour is $w(a,b)+w(b,c)+w(c,a)+w(a,d)+\cdots$. The cost of the TSP tour is $w(a,b)+w(b,c)+w(c,d)+\cdots$. The triangle inequality shows that $w(c,d) \leq w(c,a)+w(a,d)$, i.e. if we take a detour from $c$ to $d$ via $a$, that can't be shorter than going straight from $c$ to $d$.

We already know that $w(T) \leq w(H)$. What about $w(M)$? Let $v_1,\ldots,v_{2k}$ be the set odd-degree vertices in $T$, in the order in which they appear in $H$ (starting at an arbitrary vertex and an arbitrary orientation). One possible way to match them is $M_1 = (v_1,v_2),(v_3,v_4),\ldots,(v_{2k-1},v_{2k})$. Another possible way is $M_2 = (v_2,v_3),(v_4,v_5),\ldots,(v_{2k-2},v_{2k-1}),(v_{2k},v_1)$. The triangle inequality (again) shows that the edge $(v_i,v_{i+1})$ costs at most as much as the entire stretch of $H$ from $v_i$ to $v_{i+1}$. Now imagine taking $M_1$ and $M_2$, and replacing each edge with the corresponding stretch of $H$. The result is all of $H$, and so $w(M_1) + w(M_2) \leq w(H)$. Since $M$ has minimum weight, $w(M) \leq w(M_1),w(M_2)$ and so $w(M) \leq w(H)/2$. Therefore $w(T) + w(M) \leq (3/2) w(H)$.

share|improve this answer
    
Brilliant! Just brilliant! –  user6422 Feb 21 '13 at 6:07
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.