<p>The distortion of embedding any $n$-point metric in  ultrametric is at most $n-1$, and on the other hand, the distortion of embedding the path metric $P_n$ in ultrametric is at least $n-1$.</p>

<p>Similarly, if you are interested in probabilistic embedding, then by Fakcharoenphol, Rao, and Talwar result mentioned above, any $n$-point metric space probabilistically embeds in ultrametric with distortion $O(\log n)$. 
On the other hand, the distortion of probabilistically embedding $P_n$ in ultrametric is $\Omega(\log n)$.</p>

CC BY-SA 3.0
2012-01-07T20:44:50.013Z
2012-01-08T00:04:25.883Z
2012-01-08T00:04:25.883Z
Manor Mendel
<p>There is a classic <a href="http://research.microsoft.com/pubs/74347/06-journal.pdf" rel="nofollow">result</a> by Fakcharoenphol, Rao, and Talwar showing that any $n$ point metric space can be embedded into an HST metric with expected distortion $O(log\, n)$. </p>

<p>One should keep in mind that this result holds only for probabilistic embeddings, since there are metrics (such as the $n$-cycle) which will give you an $\Omega(n)$ distortion if you only accept deterministic embeddings.</p>

CC BY-SA 3.0
2012-01-07T10:51:52.467Z
Thanks. I knew the FRT result. Actually I was asking a different question. See the quesiton now. For some reason, the word "tree"  was deleted by the editor...I added it back now.
jian
CC BY-SA 3.0
2012-01-07T09:38:26.017Z
2012-01-07T09:38:26.017Z
zotachidil
<p>Is there any known result on approximating an arbitrary tree metric by an HST metric (or an Ultrametric)? What is the distortion? Thanks.</p>

CC BY-SA 3.0
2012-01-07T14:42:05.467Z
Not following: what's the difference between an HST metric and a general tree metric ?
Suresh Venkat
CC BY-SA 3.0
2012-01-09T10:26:09.170Z
An HST metric is a special tree metric. So we still want to embed a "hard" metric space into a simpler metric space.
jian
<ds.algorithms><approximation-algorithms><embeddings>
Is there any result on approximating an arbitrary tree metric by an HST metric?
jian
# Is there any result on approximating an arbitrary tree metric by an HST metric?

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

Is there any known result on approximating an arbitrary tree metric by an HST metric (or an Ultrametric)? What is the distortion? Thanks.

**Tags:** ds.algorithms, approximation-algorithms, embeddings

> **Comments:**
> **username_1**: Not following: what's the difference between an HST metric and a general tree metric ?  
> **username_0**: An HST metric is a special tree metric. So we still want to embed a "hard" metric space into a simpler metric space.  

---

## 2 answers

### Answer by username_2 on 2012-01-07. Score: 4 | Accepted answer

The distortion of embedding any $n$-point metric in ultrametric is at most $n-1$, and on the other hand, the distortion of embedding the path metric $P\_n$ in ultrametric is at least $n-1$.

Similarly, if you are interested in probabilistic embedding, then by Fakcharoenphol, Rao, and Talwar result mentioned above, any $n$-point metric space probabilistically embeds in ultrametric with distortion $O(\log n)$.
On the other hand, the distortion of probabilistically embedding $P\_n$ in ultrametric is $\Omega(\log n)$.


---

### Answer by username_3 on 2012-01-07. Score: 3

There is a classic [result](http://research.microsoft.com/pubs/74347/06-journal.pdf) by Fakcharoenphol, Rao, and Talwar showing that any $n$ point metric space can be embedded into an HST metric with expected distortion $O(log\, n)$.

One should keep in mind that this result holds only for probabilistic embeddings, since there are metrics (such as the $n$-cycle) which will give you an $\Omega(n)$ distortion if you only accept deterministic embeddings.

> **Comments:**
> **username_0**: Thanks. I knew the FRT result. Actually I was asking a different question. See the quesiton now. For some reason, the word "tree"  was deleted by the editor...I added it back now.  

---

