Metric Embeddings
with Relaxed Guarantees
I. Abraham Y. Bartal T-H. Chan K. Dhamdhere A. Gupta J. leinberg O. Neiman A. Slivkins |
|
|
Abstract We consider the problem of embedding finite
metrics with lack: we seek to produce embeddings with small dimension ad
distortion while allowing a (small) constant fraction of al 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 [29], 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 l1 which
exhibit gracefully degrading distortion: these is a single embedding into l1
that achieves distortion at most O(log 1/ε ) on all but at most an ε
fraction of distances, simultaneously for all ε > 0. We extend this
with distortion O(log 1/ε)1/p to maps into general lp,
p > 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 ε-slack
embeddings from lower bounds for low-distortion embeddings. |
||
[FOCS version pdf] |