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

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 ε, 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 lq-distortions are small. Specifically, our embeddings have constant average distortion and O(log n) l2-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 ~O(log^2 (1/ε)), which implies constant lq-distortion for every fixed q<∞.
	[Extended TR version pdf]