TITLE   : Embedding Metrics into Ultrametrics and Graphs into Spanning Trees with
Constant Average Distortion

AUTHORS : Ittai Abraham, Yair Bartal, Ofer Neiman

ABSTRACT:

This paper addresses the basic question of how well can a tree
approximate distances of a metric space or a graph. Given a graph,
the problem of constructing a spanning tree in a graph which
strongly preserves distances in the graph is a fundamental problem
in network design. We present scaling distortion embeddings where
the distortion scales as a function of $\epsilon$, with the
guarantee that for each $\epsilon$ the distortion of a fraction
$1-\epsilon$ of all pairs is bounded accordingly. Such a bound
implies, in particular, that the \emph{average distortion} and
$\ell_q$-distortions are small. Specifically, our embeddings have
\emph{constant} average distortion and $O(\sqrt{\log n})$
$\ell_2$-distortion. This follows from the following results: we
prove that any metric space embeds into an ultrametric with scaling
distortion $O(\sqrt{1/\epsilon})$. For the graph setting we prove
that any weighted graph contains a spanning tree with scaling
distortion $O(\sqrt{1/\epsilon})$.  These bounds are tight even for
embedding in arbitrary trees.
 For probabilistic embedding into spanning trees
we prove a scaling distortion of $\tilde{O}(\log^2 (1/\epsilon))$,
which implies \emph{constant} $\ell_q$-distortion for every fixed
$q<\infty$.