2
$\begingroup$

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

$\endgroup$
6
$\begingroup$

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

$\endgroup$
  • $\begingroup$ It's written in the question that a mapping expands all pairwise distances. So, your first paragraph is correct. $\endgroup$ – Yoshio Okamoto Jan 26 '12 at 1:04
  • $\begingroup$ @azotlichid, I see what you mean. Yes, these things also appear in the first lecture but (sigh), they are further down in the lecture. I guess, I asked too early. Thanks again for the clarification. -Akash $\endgroup$ – Akash Kumar Jan 26 '12 at 1:38

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.