An intuitive justification - Metric Embedding Based Approximation Algorithms

Question

Recently, I started (independent) learning of the theory of metric embeddings from the Fall 2003 course offered at CMU .

I had a very basic question from the very first lecture of this course which I would like to get more intuition about. On page, $5$, the notes say that this technique can be used in a straightforward way to give an $\alpha$ approximation algorithms for problems like TSP if (say) the following hold.

(i) The metric embeds into a tree.
(ii) The embedding has distortion at most $\alpha$

What I am not sure about is whether the solution generated by using the embedding is even valid - because for all I know, it could be that the TSP solution on the tree uses only from among those edges which were contracted.

To be more precise, I feel more comfortable accepting that if we have got a mapping $f$ from the original space $(X,d)$ to the tree metric $(V, d')$ which expands all the pairwise distances, then I can use the TSP solution on this tree as an approximate solution to the TSP problem on the original metric with approximation factor same as the expansion of the mapping $f$. I am not sure about how approximation factor can be the same as (or even related to) the distortion of the mapping $f$.

Thanks
-Akash

Answer 1

The way I remember it is that you also get a lower bound on the expected cost in the embedding. Namely for any two points $x$, $y$ at distance $d(x,y)$ in the original metric, their distance $d'(x,y)$ in the embedding satisfies $d(x,y) \leq d'(x,y)$. If I'm not mistaken, the first lecture mentions that too.

Then, everything is straightforward.

Look at the optimal TSP instance $I$ of the graph $G$. Then consider the embedding of $I$ (call it $I'$) into the tree metric. $I'$ is also an instance of TSP for the tree metric, and its cost is bounded by $E[cost(I')] \leq \alpha \cdot cost(I)$.

Therefore, if you compute $J'$, which is the optimal TSP for the tree metric, $E[cost(J')] \leq E[cost(I')] \leq \alpha \cdot cost(I)$.

Lift $J'$ back into your initial graph, which gives you an instance $J$. Thus, $cost(J) \leq E[cost(J')]$. And thus, using the previous chain of inequalities, $cost(J) \leq \alpha \cdot OPT$.