TITLE   : Metric Embeddings with Relaxed Guarantees

AUTHORS : Ittai Abraham, Yair Bartal, T-H. Hubert Chan, Kedar Dhamdhere, Anupam Gupta, Jon Kleinberg, Ofer Neiman, Aleksandrs Slivkins

ABSTRACT:

We consider the problem of embedding finite metrics with {\em 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
  \cite{KSW04}, we show that provable guarantees of this type can in
  fact be achieved in general: any finite metric 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 {\em gracefully degrading} distortion:
  these is a single embedding into $\ell_1$ that achieves distortion at
  most $O(\log\freps)$ on all but at most an $\e$ fraction of distances,
  {\em simultaneously} for all $\e > 0$. We extend this with distortion
  $O(\log\freps)^{1/p}$ to maps into general $\ell_p$, $p\geq 1$ 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 $\e$-slack embeddings from lower bounds for low-distortion
  embeddings.