Approximation algorithms for minimizing average distortion

We study the problem of embedding arbitrary finite metrics into a line metric in a non-contracting fashion to approximate the minimum average distortion. Since a path metric (or a line metric) is quite restricted, these embeddings could have high average distortions (Ω(n), where n is the number of points in the original metric). Furthermore, we prove that finding best embedding of even a tree metric into a line to minimize average distortion is NP-hard. Hence, we focus on approximating the best possible embedding for given input metric. We give a constant-factor approximation for the problem of embedding general metrics into the line metric. For the case of the metrics which can be represented as trees, we provide improved approximation ratios in polynomial time as well as a QPTAS (Quasi-Polynomial Time Approximation Scheme).