0
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Please correct me if I am wrong. A spanning tree has (n-1) edges. The cost of full walk W is twice the cost of T. As calculated from before, the extra cost from this inequality is cost(v,w) for each shortcut. Therefore, the cost of H = (the cost of W) + (n-1)cost(v,w). Comparing the cost of H to the cost of T, that makes the cost of H = 2 x (the cost of T) + (n-1)cost(v,w), and since the cost of T is less than or equal to the cost of the optimal tour, that means the cost of H is less than or equal to 2 x (the cost of the optimal tour) + (n-1)cost(v,w) $\endgroup$ – James the Great Jul 23 '15 at 7:53
  • $\begingroup$ so that makes it a (2+(n-1)cost(v,w)) approximation $\endgroup$ – James the Great Jul 23 '15 at 7:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.