Embedding Metrics into Ultrametrics and Graphs into Spanning Trees with Constant Average Distortion
<|reference_start|>Embedding Metrics into Ultrametrics and Graphs into Spanning Trees with Constant Average Distortion: 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$.<|reference_end|>
@article{abraham2006embedding,
    title={Embedding Metrics into Ultrametrics and Graphs into Spanning Trees with
  Constant Average Distortion},
    author={Ittai Abraham, Yair Bartal, Ofer Neiman},
    journal={arXiv preprint arXiv:cs/0610003},
    year={2006},
    archivePrefix={arXiv},
    eprint={cs/0610003},
    primaryClass={cs.DM}
}