Approximating Metrics by Tree Metrics of Small Distance-Weighted Average Stretch

摘要

We study the problem of how well a tree metric is able to preserve the sum ofpairwise distances of an arbitrary metric. This problem is closely related tolow-stretch metric embeddings and is interesting by its own flavor from theline of research proposed in the literature. As the structure of a tree imposes great constraints on the pairwisedistances, any embedding of a metric into a tree metric is known to havemaximum pairwise stretch of $\Omega(\log n)$. We show, however, from theperspective of average performance, there exist tree metrics which preserve thesum of pairwise distances of the given metric up to a small constant factor,for which we also show to be no worse than twice what we can possibly expect.The approach we use to tackle this problem is more direct compared to aprevious result of [4], and also leads to a provably better guarantee. Second,when the given metric is extracted from a Euclidean point set of finitedimension $d$, we show that there exist spanning trees of the given point setsuch that the sum of pairwise distances is preserved up to a constant whichdepends only on $d$. Both of our proofs are constructive. The main ingredientin our result is a special point-set decomposition which relates twoseemingly-unrelated quantities.