<p>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&#39;(x,y)$ in the embedding satisfies $d(x,y) \leq d&#39;(x,y)$. If I'm not mistaken, the first lecture mentions that too.</p>

<p>Then, everything is straightforward.</p>

<p>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&#39;$ is also an instance of TSP for the tree metric, and its cost is bounded by $E[cost(I&#39;)] \leq \alpha \cdot cost(I)$. </p>

<p>Therefore, if you compute $J&#39;$, which is the optimal TSP for the tree metric, $E[cost(J&#39;)] \leq E[cost(I&#39;)] \leq \alpha \cdot cost(I)$.</p>

<p>Lift $J&#39;$ back into your initial graph, which gives you an instance $J$. Thus, $cost(J) \leq E[cost(J&#39;)]$. And thus, using the previous chain of inequalities,  $cost(J) \leq \alpha \cdot OPT$.</p>

CC BY-SA 3.0
2012-01-26T01:04:54.903Z
It's written in the question that a mapping expands all pairwise distances. So, your first paragraph is correct.
Yoshio Okamoto
CC BY-SA 3.0
2012-01-26T01:38:47.227Z
@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
Akash Kumar
CC BY-SA 3.0
2012-01-25T23:52:35.273Z
2012-01-25T23:52:35.273Z
zotachidil
<p>Recently, I started (independent) learning of the theory of metric embeddings from the Fall 2003 course <a href="http://www.cs.cmu.edu/~anupamg/metrics/" rel="nofollow"> offered at CMU </a>.</p>

<p>I had a very basic question from the very <a href="http://www.cs.cmu.edu/~anupamg/metrics/lectures/lec1.ps" rel="nofollow"> first lecture </a> 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.</p>

<p>(i) The metric embeds into a tree.<br>
(ii) The embedding has distortion at most $\alpha$</p>

<p>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.</p>

<p>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&#39;)$ 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$.  </p>

<p>Thanks<br>
-Akash</p>

<approximation-algorithms><metric-spaces><intuition>
An intuitive justification - Metric Embedding Based Approximation Algorithms
Akash Kumar
# An intuitive justification - Metric Embedding Based Approximation Algorithms

(Asked by: username_0 on 2012-01-25)

Recently, I started (independent) learning of the theory of metric embeddings from the Fall 2003 course  [offered at CMU](http://www.cs.cmu.edu/~anupamg/metrics/) .

I had a very basic question from the very  [first lecture](http://www.cs.cmu.edu/~anupamg/metrics/lectures/lec1.ps)  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

**Tags:** approximation-algorithms, metric-spaces, intuition


---

## 1 answers

### Answer by username_1 on 2012-01-25. Score: 6 | Accepted answer

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

> **Comments:**
> **username_2**: It's written in the question that a mapping expands all pairwise distances. So, your first paragraph is correct.  
> **username_0**: @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  

---

