0
$\begingroup$

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$.

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ 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)$. $\endgroup$
    – Chandra Chekuri
    Apr 22 at 20:52
  • $\begingroup$ 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 $\endgroup$
    – Neal Young
    Apr 23 at 2:39
  • $\begingroup$ 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. $\endgroup$
    – usul
    Apr 23 at 3:43

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy