Metric Embeddings with Relaxed Guarantees
Venue
SIAM Journal on Computing, vol. 38 (2009), pp. 2303-2329
Publication Year
2009
Authors
T H Hubert Chan, Kedar Dhamdhere, Anupam Gupta, Jon m Kleinberg, Aleksandrs Slivkins
BibTeX
Abstract
We consider the problem of embedding finite metrics with slack: We seek to produce
embeddings with small dimension and distortion while allowing a (small) constant
fraction of all distances to be arbitrarily distorted. This definition is motivated
by recent research in the networking community, which achieved striking empirical
success at embedding Internet latencies with low distortion into low-dimensional
Euclidean space, provided that some small slack is allowed. Answering an open
question of Kleinberg, Slivkins, and Wexler [in Proceedings of the 45th IEEE
Symposium on Foundations of Computer Science, 2004], we show that provable
guarantees of this type can in fact be achieved in general: Any finite metric space
can be embedded, with constant slack and constant distortion, into
constant-dimensional Euclidean space. We then show that there exist stronger
embeddings into $\ell_1$ which exhibit gracefully degrading distortion: There is a
single embedding into $\ell_1$ that achieves distortion at most
$O(\log\frac{1}{\epsilon})$ on all but at most-1.5pt an $\epsilon$ fraction of
distances simultaneously for all $\epsilon>0$. We extend this with distortion1pt
$O(\log\frac{1}{\epsilon})^{1/p}$ to maps into general $\ell_p$, $p\geq1$, for
several classes of metrics, including those with bounded doubling dimension and
those arising from the shortest-path metric of a graph with an excluded minor.
Finally, we show that many of our constructions are tight and give a general
technique to obtain lower bounds for $\epsilon$-slack embeddings from lower bounds
for low-distortion embeddings.
