Approximating arbitrary metric by tree metric

a distribution over dominating tree metrics such that the expected
stretch of each edge is O(\log n) (this result is existentially tight
also). The authors first give a very simple deterministic algorithm with
intuitive appeal which computes a dominating tree metric for a given
metric. However, the stretch of an edge of the original metric in this
tree metric may be quite high. After that, they use simple randomization
in a powerful way to ensure that expected stretch of an edge in the tree
metric is O(\log n). Overall the algorithm is short, simple, and its
analysis is really beautiful.

Reference: Approximating arbitrary metric by tree metric (Fakcharenphol, Satish Rao, and Kunal Talwar, JCSS 2004, STOC 2003)