Metric Embeddings with Relaxed Guarantees

We consider the problem of embedding finite metrics with slack: we seek to produce embeddingswith 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.