I have an Approximation Algorithm problem and its answer but I am having a hard time to clearly understand.
The problem is as follows:

Consider the following closest-point heuristic for building an approximate traveling-salesman tour whose cost function satisfies the triangle inequality. Begin with a trivial cycle consisting of a single arbitrarily chosen vertex. At each step, identify the vertex $u$ that is not on the cycle but whose distance to any vertex on the cycle is minimum. Suppose that the vertex on the cycle that is nearest $u$ is vertex $v$. Extend the cycle to include $u$ by inserting $u$ just after $v$. Repeat until all vertices are on the cycle. Prove that this heuristic returns a tour whose total cost is not more than twice the cost of an optimal tour.

The answer is (I apoligize for including an image but I couldn´t get the some special characters displayed correctly)

enter image description here

What I do not understand is the part surrounded by the red rectangle. I will very much appreciate if you help me to get the idea behind it. I am studying for an exam and I am stuck with this problem.

Jorge Maldonado


1 Answer 1


I think there's some problem with the LaTeX formula. It should look like this:

$c(H_i)\leq c(H_{i-1})+2c(u_i, v_i)$

Let's say initially it was $u\to x$. Then you add $v$ directly after $u$, forming $u\to v\to x$. This increases the total distance by $c(u,v)+c(v,x)-c(u,x)$. From the triangle inequality, we have $c(u,v) + c(u,x) \geq c(v,x)$ and thus $2c(u,v)\geq c(u,v)+c(v,x)-c(u,x)$, hence $c(H_i)\leq c(H_{i-1})+2c(u_i, v_i)$.

The next paragraph should make more sense now.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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