Probabilistic Approximation of Metrics by Tree Metrics

Consider a finite set $V$ and a function $d: V \times V \rightarrow \mathbb{R}$ such that $(V,d)$ forms a metric space. A function $d_T : V' \times V' \rightarrow \mathbb{R}$ is called a tree metric on $V'$ if for all $u,v \in V'$, $d_T(u,v)$ is the length of the unique shortest path between them in $T$, where $T$ is a tree on $V'$ with nonnegative lengths on its edges. A well studied problem in literature is to approximate a given metric $d$ on $V$ using some tree metric $d_T$ on $V' \supseteq V$ in the sense that $d(u,v) \le d_T(u,v) \le \alpha d(u,v)$ for all $u,v \in V$ and for some $\alpha$. In this talk, I will present the result of Fakcharoenphol et al. that there is a randomized polynomial time algorithm which, given any metric $d$ on an $n$-sized set $V$, produces a tree metric $d_T$ on some $V' \supseteq V$, such that for all $u,v \in V$, $d(u,v) \le d_T(u,v)$ and $E[d_T(u,v)] \le O(\log n) d(u,v)$.