3
$\begingroup$

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

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

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

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – jian Jan 7 '12 at 10:51

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.