  We study the problem of how well a tree metric is able to preserve the sum of
pairwise distances of an arbitrary metric. This problem is closely related to
low-stretch metric embeddings and is interesting by its own flavor from the
line of research proposed in the literature.
  As the structure of a tree imposes great constraints on the pairwise
distances, any embedding of a metric into a tree metric is known to have
maximum pairwise stretch of $\Omega(\log n)$. We show, however, from the
perspective of average performance, there exist tree metrics which preserve the
sum 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 a
previous result of [4], and also leads to a provably better guarantee. Second,
when the given metric is extracted from a Euclidean point set of finite
dimension $d$, we show that there exist spanning trees of the given point set
such that the sum of pairwise distances is preserved up to a constant which
depends only on $d$. Both of our proofs are constructive. The main ingredient
in our result is a special point-set decomposition which relates two
seemingly-unrelated quantities.
