approximation algorithm for Travelling Salesman Problem: with a different inequality and not triangle inequality

Question

I have the following question for the travelling salesman problem:

The TSP algorithm is to find a complete hamilton cycle with minimum cost in a weighted graph G. Instead of the traingle inequality, the weight function satisfies the following inequality:

cost(u,w) < cost(u,v) + 2 x cost(v,w)

Find the approximation ratio if we use the following approximation algorithm:

1. Select any vertex as root vertex
2. Compute a minimum spanning tree T from graph G
3. Let L be the list of vertices visited in a preorder tree walk of T
4. return the hamilton cycle H that visits the vertices in the order L

My work so far

I figured out that it is 2-approximation if it is the triangle inequality, since going directly from one vertex to another has a cost no greater than going to a vertex in between these two vertices, so cost(H) is not greater than the cost of the preorder tree walk and therefore no greater than twice the cost of the optimal tour.

However, inequality cost(u,w) < cost(u,v) + 2 x cost(v,w) would make it different than triangle inequality that going directly from u to w could result in higher cost than from u to v to w (unless cost(v,w)=0). I think the worst case is extra cost of cost(u,v) + 2 x cost(v,w) - (cost(u,v) + cost(v,w))= cost(v,w)

Any advice on this? I need to find the approximation ratio.

Answer 1

Review the standard proof that it's a 2-approximation if the weight function satisfies the triangle inequality. That suggests a way to upper-bound the total length of the Hamilton cycle $H$ returned by the algorithm.

Adjust that reasoning. For starters, assume that every edge in $H$ is a "shortcut edge" $(u,w)$ that was taken by skipping a single vertex $v$. What could you conclude about the cost of $H$, compared to the cost of $T$? If you do a little bit of algebra you should be able to obtain an expression.

Now generalize to arbitrary $H$.