In TSP where a modified triangle inequality holds, what is the approximation ratio of Christofides' algorithm?

58 Views Asked by At

In the metric TSP, we can use Christofides' algorithm to get a $\frac{3}{2}$-approximate solution. This is a consequence of the triangle inequality where $d_{ij} + d_{jl} \geq d_{il}$, that enables us to a) use shortcutting, and b) combine the edges of the minimum dominating set and the minimum spanning tree (MST). We know that the cost of the MST is $\le OPT$ (where OPT is the cost of the optimal tour), and for the minimum dominating set $\leq \frac{1}{2} OPT$. Therefore constructing a union and shortcutting duplicate edges results in an upperbound of $\frac{3}{2}OPT$.

Now, if we were to assume that triangle inequality does not hold, but instead we have this weaker version:

$$ d_{ij}+d_{jl} \geq \frac{d_{il}}{c}$$

What is the upperbound on the approximation ratio?

We know that the tour from the union has a cost $\frac{1}{2}\sum_{ijl} d_{ij}+d_{jl} \leq \frac{3}{2}OPT$ $\implies $ the tour after shortcutting has an upperbound $\frac{3c}{2}OPT$. The summation ads adjacent edges in the tour, and therefore double counts everything, hence the $\frac{1}{2}$ fraction.

Is this sketch correct?