Title: On Notions of Distortion and an Almost Minimum Spanning Tree with Constant Average Distortion

Authors: Yair Bartal, Arnold Filtser and Ofer Neiman.

Abstract: This paper makes two main contributions: The first is the construction of a {\sl near-minimum spanning tree} with {\sl constant average distortion}. 
The second is a general equivalence theorem relating two refined notions of distortion: {\sl scaling distortion} and {\sl prioritized distortion}.
		
		

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{ABN15} 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)$. Our result exhibits the best possible tradeoff of this type.


This result makes use of a {\em general equivalence theorem} relating two recently developed notions of distortion for metric embedding.
		
The first is the notion of {\em scaling distortion}, which provides improved distortion for $1-\epsilon$ fractions of the pairs, for all $\epsilon$ simultaneously. 
A stronger version called {\em coarse} scaling distortion, has improved distortion guarantees for the furthest pairs.
 The second notion is that of 
{\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 coarse scaling distortion via a general transformation.
		
		

Our spanning tree result is achieved by first showing the existence of a low weight {\em spanner} with small prioritized distortion, which by our theorem implies scaling 
distortion, which in turn implies the constant average distortion bound.
 The scaling-prioritized distortion equivalence theorem has further implications and is of
independent interest. In particular, it allows us to resolve a few questions concerning prioritized embedding. Mainly, we obtain a strengthening of Bourgain's theorem on 
embedding arbitrary metrics into Euclidean space, possessing optimal prioritized distortion.