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

Browse other questions tagged or ask your own question.