# Is there any result on approximating an arbitrary tree metric by an HST metric?

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

• Not following: what's the difference between an HST metric and a general tree metric ? – Suresh Venkat Jan 7 '12 at 14:42
• An HST metric is a special tree metric. So we still want to embed a "hard" metric space into a simpler metric space. – jian Jan 9 '12 at 10:26

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)$.
There is a classic result 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.