eCommons@Cornell >
Faculty of Computing and Information Science >
Computing and Information Science >
Computing and Information Science Technical Reports >
Please use this identifier to cite or link to this item:
http://hdl.handle.net/1813/5741
Title:  Metric Embeddings with Relaxed Guarantees 
Authors:  Chan, TH. Hubert Dhamdhere, Kedar Gupta, Anupam Kleinberg, Jon Slivkins, Aleksandrs Aleksandrs Slivkins 
Keywords:  computer science technical report 
Issue Date:  22Sep2006 
Publisher:  Cornell University 
Citation:  http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cis/TR20062044 
Abstract:  We consider the problem of embedding finite metrics with "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 lowdimensional Euclidean space, provided that some small slack is allowed. Answering an open question of [Kleinberg, Slivkins, and Wexler, IEEE FOCS 2004], 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 constantdimensional 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/epsilon) on all but at most an epsilonfraction of distances, *simultaneously* for all epsilon greater than 0. We extend this with distortion O(log 1/epsilon)^{1/p} to maps into general Lp, p greater than or equal to 1 for several classes of metrics, including those with bounded doubling dimension and those arising from the shortestpath 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 epsilonslack embeddings from lower bounds for lowdistortion embeddings. 
URI:  http://hdl.handle.net/1813/5741 
Appears in Collections:  Computing and Information Science Technical Reports

Items in eCommons are protected by copyright, with all rights reserved, unless otherwise indicated.
