File Download
There are no files associated with this item.
Links for fulltext
(May Require Subscription)
- Publisher Website: 10.1109/SFCS.2005.51
- Scopus: eid_2-s2.0-33748589199
- Find via
Conference Paper: Metric embeddings with relaxed guarantees
Title | Metric embeddings with relaxed guarantees |
---|---|
Authors | |
Keywords | Finite Element Method Graph Theory Internet Mathematical Models Problem Solving |
Issue Date | 2005 |
Citation | Proceedings - Annual Ieee Symposium On Foundations Of Computer Science, Focs, 2005, v. 2005, p. 83-100 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 [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 e 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. ©2005 IEEE. |
Persistent Identifier | http://hdl.handle.net/10722/92651 |
ISSN | 2020 SCImago Journal Rankings: 2.949 |
References |
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Abraham, I | en_HK |
dc.contributor.author | Bartal, Y | en_HK |
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 | Neiman, O | en_HK |
dc.contributor.author | Slivkins, A | en_HK |
dc.date.accessioned | 2010-09-17T10:53:04Z | - |
dc.date.available | 2010-09-17T10:53:04Z | - |
dc.date.issued | 2005 | en_HK |
dc.identifier.citation | Proceedings - Annual Ieee Symposium On Foundations Of Computer Science, Focs, 2005, v. 2005, p. 83-100 | en_HK |
dc.identifier.issn | 0272-5428 | en_HK |
dc.identifier.uri | http://hdl.handle.net/10722/92651 | - |
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 [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 e 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. ©2005 IEEE. | en_HK |
dc.language | eng | en_HK |
dc.relation.ispartof | Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS | en_HK |
dc.subject | Finite Element Method | en_HK |
dc.subject | Graph Theory | en_HK |
dc.subject | Internet | en_HK |
dc.subject | Mathematical Models | en_HK |
dc.subject | Problem Solving | en_HK |
dc.title | Metric embeddings with relaxed guarantees | en_HK |
dc.type | Conference_Paper | en_HK |
dc.identifier.email | Chan, THH:hubert@cs.hku.hk | en_HK |
dc.identifier.authority | Chan, THH=rp01312 | en_HK |
dc.description.nature | link_to_subscribed_fulltext | - |
dc.identifier.doi | 10.1109/SFCS.2005.51 | en_HK |
dc.identifier.scopus | eid_2-s2.0-33748589199 | en_HK |
dc.relation.references | http://www.scopus.com/mlt/select.url?eid=2-s2.0-33748589199&selection=ref&src=s&origin=recordpage | en_HK |
dc.identifier.volume | 2005 | en_HK |
dc.identifier.spage | 83 | en_HK |
dc.identifier.epage | 100 | en_HK |
dc.identifier.scopusauthorid | Abraham, I=7102212547 | en_HK |
dc.identifier.scopusauthorid | Bartal, Y=7006542888 | 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 | Neiman, O=14525717700 | en_HK |
dc.identifier.scopusauthorid | Slivkins, A=8407870700 | en_HK |
dc.identifier.citeulike | 3081677 | - |
dc.identifier.issnl | 0272-5428 | - |