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.
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.