# Does the Christofides algorithm ensure this inequality?

Let $$(X,d)$$ be a finite metric space. Let $$C$$ be a Hamiltonian cycle (over $$X$$) outputted by Christofide's algorithm. Also, let $$K$$ be a minimum spanning tree. I am aware that Christofide's algorithm is a $$\frac{3}{2}$$ approximation algorithm. But does the following also holds

$$l(C) \le \frac{3}{2} l(K)$$

where $$l(.)$$ denotes the cost, interpreted in a natural way. I do not see why it should hold, but this paper seems to use this as a fact in theorem $$5$$.

• The claim is false for general metric spaces. Take a path on $n$ vertices with unit edge lengths, and $d$ is the shortest path metric induced by this graph. The MST cost is $(n-1)$ while the optimum TSP cost is $2(n-1)$. Apr 22 at 20:52
• The OP does seem to be correct that a line in the proof of Theorem 5 in that paper states that the cycle C has total weight at most (3/2) times the weight of the spanning tree. And Chandra does seem to be right that this doesn't hold in general. So I think OP's question is reasonable. Here is a doi link to the paper: doi.org/10.1007/s003730070012 Apr 23 at 2:39
• Yes, seems like that paper mis-states Christofide's result to be $l(C) \leq (3/2) l(K)$, when the result is only $l(C) \leq (3/2) OPT$ where OPT is the optimal TSP solution.
– usul
Apr 23 at 3:43