<p>Let <span class="math-container">$(X,d)$</span> be a finite metric space. Let <span class="math-container">$C$</span> be a Hamiltonian cycle (over <span class="math-container">$X$</span>) outputted by Christofide's algorithm. Also, let <span class="math-container">$K$</span> be a minimum spanning tree. I am aware that Christofide's algorithm is a <span class="math-container">$\frac{3}{2}$</span> approximation algorithm. But does the following also holds</p>
<p><span class="math-container">$$l(C) \le \frac{3}{2} l(K)$$</span></p>
<p>where <span class="math-container">$l(.)$</span> denotes the cost, interpreted in a natural way. I do not see why it should hold, but
<a href="https://ur.booksc.me/book/7553484/af4a2c" rel="nofollow noreferrer">this</a> paper seems to use this as a fact in theorem <span class="math-container">$5$</span>.</p>

CC BY-SA 4.0
2022-04-22T20:52:47.703Z
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)$.
Chandra Chekuri
CC BY-SA 4.0
2022-04-23T02:39:28.383Z
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: https://doi.org/10.1007/s003730070012
Neal Young
CC BY-SA 4.0
2022-04-23T03:43:58.850Z
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
<graph-theory><graph-algorithms><approximation-algorithms><metric-spaces>
Does the Christofides algorithm ensure this inequality?
advocateofnone
# Does the Christofides algorithm ensure this inequality?

(Asked by: username_0 on 2022-04-22)

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](https://ur.booksc.me/book/7553484/af4a2c) paper seems to use this as a fact in theorem $5$.

**Tags:** graph-theory, graph-algorithms, approximation-algorithms, metric-spaces

> **Comments:**
> **username_1**: 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)$.  
> **username_2**: 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: https://doi.org/10.1007/s003730070012  
> **username_3**: 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.  

---

## 0 answers

