File Download
Links for fulltext
(May Require Subscription)
- Publisher Website: 10.1137/060670511
- Scopus: eid_2-s2.0-65949122721
- WOS: WOS:000266018400008
- Find via
Supplementary
- Citations:
- Appears in Collections:
Article: Metric embeddings with relaxed guarantees
Title | Metric embeddings with relaxed guarantees | ||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|
Authors | |||||||||||
Keywords | Low-distortion embeddings Metric decompositions Metric embeddings Metric spaces Randomized algorithms | ||||||||||
Issue Date | 2009 | ||||||||||
Publisher | Society for Industrial and Applied Mathematics. The Journal's web site is located at http://www.siam.org/journals/sicomp.php | ||||||||||
Citation | SIAM Journal On Computing, 2009, v. 38 n. 6, p. 2303-2329 How to Cite? | ||||||||||
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 low-dimensional Euclidean space, provided that some small slack is allowed. Answering an open question of Kleinberg, Slivkins, and Wexler [in Proceedings of the 45th IEEE Symposium on Foundations of Computer Science, 2004], we show that provable guarantees of this type can in fact be achieved in general: Any finite metric space can be embedded, with constant slack and constant distortion, into constant-dimensional Euclidean space. We then show that there exist stronger embeddings into l 1 which exhibit gracefully degrading distortion: There is a single embedding into l 1 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 l p, 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. © 2009 Society for Industrial and Applied Mathematics. | ||||||||||
Persistent Identifier | http://hdl.handle.net/10722/92628 | ||||||||||
ISSN | 2023 Impact Factor: 1.2 2023 SCImago Journal Rankings: 2.143 | ||||||||||
ISI Accession Number ID |
Funding Information: This work was done when this author was a graduate student at Carnegie Mellon University and was supported in part by NSF ITR CCR-0122581 (The ALADDIN project) and also by the NSF career award and an Alfred P. Sloan Fellowship of Anupam Gupta. | ||||||||||
References |
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Chan, THH | en_HK |
dc.contributor.author | Dhamdhere, K | en_HK |
dc.contributor.author | Gupta, A | en_HK |
dc.contributor.author | Kleinberg, J | en_HK |
dc.contributor.author | Slivkins, A | en_HK |
dc.date.accessioned | 2010-09-17T10:52:22Z | - |
dc.date.available | 2010-09-17T10:52:22Z | - |
dc.date.issued | 2009 | en_HK |
dc.identifier.citation | SIAM Journal On Computing, 2009, v. 38 n. 6, p. 2303-2329 | en_HK |
dc.identifier.issn | 0097-5397 | en_HK |
dc.identifier.uri | http://hdl.handle.net/10722/92628 | - |
dc.description.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 low-dimensional Euclidean space, provided that some small slack is allowed. Answering an open question of Kleinberg, Slivkins, and Wexler [in Proceedings of the 45th IEEE Symposium on Foundations of Computer Science, 2004], we show that provable guarantees of this type can in fact be achieved in general: Any finite metric space can be embedded, with constant slack and constant distortion, into constant-dimensional Euclidean space. We then show that there exist stronger embeddings into l 1 which exhibit gracefully degrading distortion: There is a single embedding into l 1 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 l p, 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. © 2009 Society for Industrial and Applied Mathematics. | en_HK |
dc.language | eng | en_HK |
dc.publisher | Society for Industrial and Applied Mathematics. The Journal's web site is located at http://www.siam.org/journals/sicomp.php | - |
dc.relation.ispartof | SIAM Journal on Computing | en_HK |
dc.rights | © 2009 Society for Industrial and Applied Mathematics. First Published in SIAM Journal on Computing in volume 38, issue 6, published by the Society for Industrial and Applied Mathematics (SIAM). | - |
dc.subject | Low-distortion embeddings | en_HK |
dc.subject | Metric decompositions | en_HK |
dc.subject | Metric embeddings | en_HK |
dc.subject | Metric spaces | en_HK |
dc.subject | Randomized algorithms | en_HK |
dc.title | Metric embeddings with relaxed guarantees | en_HK |
dc.type | Article | en_HK |
dc.identifier.email | Chan, THH:hubert@cs.hku.hk | en_HK |
dc.identifier.authority | Chan, THH=rp01312 | en_HK |
dc.description.nature | published_or_final_version | - |
dc.identifier.doi | 10.1137/060670511 | en_HK |
dc.identifier.scopus | eid_2-s2.0-65949122721 | en_HK |
dc.relation.references | http://www.scopus.com/mlt/select.url?eid=2-s2.0-65949122721&selection=ref&src=s&origin=recordpage | en_HK |
dc.identifier.volume | 38 | en_HK |
dc.identifier.issue | 6 | en_HK |
dc.identifier.spage | 2303 | en_HK |
dc.identifier.epage | 2329 | en_HK |
dc.identifier.eissn | 1095-7111 | - |
dc.identifier.isi | WOS:000266018400008 | - |
dc.publisher.place | United States | en_HK |
dc.identifier.scopusauthorid | Chan, THH=12645073600 | en_HK |
dc.identifier.scopusauthorid | Dhamdhere, K=8593470600 | en_HK |
dc.identifier.scopusauthorid | Gupta, A=8354044800 | en_HK |
dc.identifier.scopusauthorid | Kleinberg, J=7005755823 | en_HK |
dc.identifier.scopusauthorid | Slivkins, A=8407870700 | en_HK |
dc.identifier.issnl | 0097-5397 | - |