posted on 1973-01-01, 00:00authored byIttai 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.