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 , with the guarantee that for each the distortion of a fraction 1 − of all pairs is bounded accordingly. Such a bound implies, in particular, that the average distortion and qdistortions are small. Specifically, our embeddings have constant average distortion and O( √ log n) 2 -distortion. This follows from the following results: we prove that any metric space embeds into an ultrametric with scaling distortion O( 1/ ). For the graph setting we prove that any weighted graph contains a spanning tree with scaling distortion O( 1/ ). These bounds are tight even for embedding in arbitrary trees. For probabilistic embedding into spanning trees we prove a scaling distortion ofÕ(log 2 (1/ )), which implies constant qdistortion for every fixed q < ∞.
For the non-contractive case REF proves that any metric space embeds into an ultrametric with small "scaling distortion", which is O(1)-approximately optimal.
Embedding metrics into ultrametrics and graphs into spanning trees with constant average distortion
SODA '07
Mathematics Computer Science