# TSP 200-approximation, given $c(x,z)\le c(x,y) + 100\cdot c(y,z)$ for all nodes $x,y,z$

Input: complete, undirected graph $$G=(V,E)$$ and cost function $$c$$ Assume for all nodes $$x,y,z \in V$$: $$c(x,z)\le c(x,y) + 100\cdot c(y,z)$$

Find a 200-approximation polynomial time algorithm for the input.

I've seen the regular 2-approximation algorithm for a graph that satisfies the triangle inequality.

1. Find the MST $$T$$ for the graph
2. Find Euler Cycle by doubling the edges in $$T$$
3. Find Hamiltonian Cycle by removing each vertex that appears more than once

If $$c(x,z)\le c(x,y) + 100\cdot c(y,z)$$ , then $$c(x,z)\le c(x,y) + c(y,z)$$ , so I figure we can use the same approximation algorithm. But I'm not sure how to prove that this gives a 200-approximation.

This is not true.

If $$c(x,z)\le c(x,y) + 100\cdot c(y,z)$$ , then $$c(x,z)\le c(x,y) + c(y,z)$$

However it is true that, for $$x,z \in V$$ with $$x \neq z$$, you have $$c(x,z) \le 100 d(x,z)$$. To see this let $$P$$ be a shortest path from $$x$$ to $$z$$. The proof is by induction on the number of edges $$|P|$$ of $$P$$.

If $$|P|=1$$ then $$c(x,z) = d(x,z) \le 100 d(x,z)$$.

If $$|P| \ge 2$$ then, let $$y$$ be the vertex immediately preceding $$z$$ in $$P$$. By inductive hypothesis $$c(x, y) \le 100 d(x,y)$$ and you have $$c(x,z) \le c(x,y) + 100 c(y,z) \le 100 d(x,y) + 100 c(y,z) =100 d(x,z). \quad \square$$

Consider a MST $$M$$ of $$G$$ and let $$T$$ be a Euler tour of $$M$$, starting from an arbitrary vertex. Let $$v_0, v_1, \dots, v_{n-1}$$ be the vertices in $$V$$ in the order they appear for the first time in $$T$$ and let $$v_n = v_0$$. Consider the tour $$T'$$ that visits $$v_0, v_1, \dots, v_n$$ in this order.

For $$i=0, \dots, n-1$$ let $$T_i$$ be the portion of the tour between the first occurrence of $$v_i$$ in $$T$$ and the next occurrence of $$v_{i+1}$$ in $$T$$. Given any graph $$H$$, let $$c(H)$$ be the sum of costs of the edges in $$H$$. Let $$T^*$$ an optimal tour of $$G$$.

You have: \begin{align*} c(T') &= \sum_{i=0}^{n-1} c(v_i, v_{i+1}) \le 100 \sum_{i=0}^{n-1} d(v_i, v_{i+1}) \le 100 \sum_{i=0}^{n-1} c(T_i) \\ &\le 100 c(T) \le 200 c(M) \le 200 c(T^*). \end{align*}