Title: Volume in General Metric Spacess

Authors: Ittai Abraham, Yair Bartal, Ofer Neiman and Leonard Schulman

Abstract:

A central question in the geometry of finite metric spaces is how
well can an arbitrary metric space be ``faithfully preserved'' by
a mapping into Euclidean space. In this paper we present an
algorithmic embedding which obtains a new strong measure of
faithful preservation: not only does it (approximately) preserve
distances between pairs of points, but also the volume of any set
of $k$ points. Such embeddings are known as volume preserving
embeddings. We provide the first volume preserving embedding that
obtains \emph{constant} average volume distortion for sets of any
fixed size. Moreover, our embedding provides constant bounds on
all bounded moments of the volume distortion. This result can be
viewed in the framework of coarse geometry where we would like to
take a ``high level" view of the space by preserving its structure
at large distances while allowing partial loss of the local
structure observed at short distances.

Feige, in his seminal work on volume preserving embeddings defined
the volume of a set $S = \{v_1, \ldots, v_k \}$ of points in a
general metric space: the product of the distances from $v_i$ to
$\{ v_1, \dots, v_{i-1} \}$, normalized by $\frac{1}{(k-1)!}$,
where the ordering of the points is that given by Prim's minimum
spanning tree algorithm. Feige also related this notion to the
maximal Euclidean volume that a Lipschitz embedding of $S$ into
Euclidean space can achieve. Syntactically this definition is
similar to the computation of volume in Euclidean spaces, which
however is invariant to the order in which the points are taken.
We show that a similar robustness property holds for Feige's
definition: the use of any other order in the product affects
volume$^{1/(k-1)}$ by only a constant factor.
Our robustness result is of independent interest as it presents a
new competitive analysis for the greedy algorithm on a variant of
the online Steiner tree problem where the cost of buying an edge
is logarithmic in its length.

This robustness property allows us
to show that there exist embeddings of general metric spaces into
Euclidean space that faithfully preserve the volume of subsets of
the original space in a strong way: simultaneously assuring
\emph{constant} average volume distortion for sets of any fixed
size, and moreover the $\ell_q$-volume distortion is
\emph{constant} for any fixed $q<\infty$, while at the same time
the embedding maintains the best possible worst-case volume
distortion.