Approximation Algorithms for Minimizing Average Distortion

This paper considers embeddings f of arbitrary finite metrics into the line metric ℜ so that none of the distances is shrunk by the embedding f; the quantity of interest is the factor by which the average distance in the metric is stretched. We call this quantity the average distortion of the non-contracting map f. We prove that finding the best embedding of even a tree metric into a line metric to minimize the average distortion is NP-hard, and hence focus on approximating the average distortion of the best possible embedding for the given input metric. We give a constant-factor approximation for the problem of embedding general metrics into the line metric. For the case of n-point tree metrics, we provide a quasi-polynomial time approximation scheme which outputs an embedding with distortion at most (1 + ε) times the optimum in time n^{O(log n/ε^2)}. Finally, when the average distortion is measured only over the endpoints of the edges of an input tree metric, we show how to exploit the structure of tree metrics to give an exact solution in polynomial time