file.pdf (283.68 kB)
Metric Embeddings with Relaxed Guarantees
journal contributionposted on 1973-01-01, 00:00 authored by Ittai Abraham, Yair Bartal, T.H. Hubert Chan, Kedar Dhamdhere, Anupam Gupta, John Kleinberg, Ofer Neiman, Aleksandrs Slivkins
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.