Title: On Notions of Distortion and an Almost Minimum Spanning Tree with Constant Average Distortion
Authors: Yair Bartal, Arnold Filtser and Ofer Neiman.
Abstract: Minimum Spanning Trees of weighted graphs are fundamental objects in numerous applications. In particular
in distributed networks, the minimum spanning tree of the network is often used to route messages between network nodes.
Unfortunately, while being most efficient in the total cost of connecting all nodes, minimum spanning trees fail miserably
in the desired property of approximately preserving distances between pairs.
While known lower bounds exclude the possibility
of the worst case distortion of a tree being small, it was shown in \cite{ABN07} that there exists a spanning tree with
constant average distortion. Yet, the weight of such a tree may be significantly larger than that of the MST.
In this paper
we show that any weighted undirected graph admits a {\em spanning tree} whose weight is at most $(1+\rho)$ times that of
the MST, providing {\em constant average distortion} $O(1/\rho^2)$.
The constant average distortion bound is implied by a
stronger property of {\em scaling distortion}, i.e., improved distortion for smaller fractions of the pairs.
The result is
achieved by first showing the existence of a low weight {\em spanner} with small {\em prioritized distortion}, a property
allowing to prioritize the nodes whose associated distortions will be improved. We show that prioritized distortion is
essentially equivalent to a strong (coarse) version of scaling distortion via a general transformation, which has further
implications and may be of independent interest. In particular, we obtain an embedding for arbitrary metrics into Euclidean
space with optimal prioritized distortion.