4
$\begingroup$

In the text book, Introduction to Algorithm, 3rd Edition.

In the chapter, Approximation Algorithms and for the problem Travelling Salesman Problem, the author says:

enter image description here

I am wondering how triangle inequality gives rise to this assertion? It seems that this property is not that important, as I searched through the rest of this section, it does not appear.

$\endgroup$
  • 1
    $\begingroup$ Check again - the approximation algorithms (or rather their analysis) implicitly use the triangle inequality in one form or the other. $\endgroup$ – Yuval Filmus Oct 16 '13 at 17:53
  • $\begingroup$ it does not seem to be stated clearly... need more info on what the cost function is computing... cost of a tour? what is its formula? etc.. are you talking about CLRS? $\endgroup$ – vzn Oct 16 '13 at 20:19
4
$\begingroup$

Here is what these lecture notes have to say. We can reduce HAMILTONIAN-PATH to MIN-TSP-TOUR in the following way: give the weight $1$ for edges in the original graph, and $B$ (for some $B > 1$ to be chosen later) for edges not in the original graph. If the original graph had a Hamiltonian path, then the new path has a tour of length at most $n$, and otherwise any tour has length at least $n-1+B$. Thus any approximation algorithm with ratio better than $n/(n-1+B)$ would solve HAMILTONIAN-PATH. Choosing $B = 1 + (c-1)n$, we get then any algorithm with ratio better than $1/c$ would solve HAMILTONIAN-PATH. This is true for any $c > 1$, so MIN-TSP-TOUR cannot be approximated to any constant ratio.


Here is where the triangle inequality comes in in Christofides' algorithm. The algorithm is at follows:

  1. Construct a minimum spanning tree $T$.
  2. Find a minimum matching $M$ between the set $O$ of odd-degree vertices in $T$.
  3. Remove edges from $T\cup M$ to obtain a Hamiltonian cycle $H$.

The analysis goes like this. Suppose $H^*$ is a Hamiltonian cycle of weight $w(H)$. Then $w(T) \leq w(H^*)$ and $w(H) \leq w(T \cup M) \leq w(T) + w(M) \leq w(H^*) + w(M)$. So far we haven't used the triangle inequality. Now take $H^*$ and replace paths from adjacent vertices $a,b \in O$ on $H^*$ with direct edges. The triangle inequality implies that the resulting cycle $H^{**}$ satisfies $w(H^{**}) \leq w(H^*)$. We can partition the cycle into two matchings $M_1,M_2$ satisfying $w(M_1) + w(M_2) = w(H^{**})$, and so $w(M) \leq \min(w(M_1),w(M_2)) \leq w(H^{**}) \leq w(H^*)$. We conclude that $w(H) \leq w(H^*) + w(M) \leq 1.5 w(H^*)$.

$\endgroup$
  • $\begingroup$ ok, but where does the triangle inequality come in? do you have a copy of CLRS? is the above quote taken from it? $\endgroup$ – vzn Oct 17 '13 at 23:02
  • 1
    $\begingroup$ @vzn I added an explanation where the triangle inequality comes in when analyzing Christofides' algorithm, which is probably what they describe in CLRS. (My notation is probably different.) $\endgroup$ – Yuval Filmus Oct 18 '13 at 0:47
1
$\begingroup$

We have been puzzled by the exact same question in the past few days. At the end, it seems that the reason why metric TSP is approximable is actually not the triangle inequality itself, but the more subtle and implied assumption that one never needs to return twice to the same city (thanks to the inequality, which also implies a all edges do exist). In fact, if you allow several visits of the cities, then it seems that even the general variant of TSP becomes approximable (see this answer to a related question).

$\endgroup$

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.