File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Conference Paper: Metric embeddings with relaxed guarantees

TitleMetric embeddings with relaxed guarantees
Authors
KeywordsFinite Element Method
Graph Theory
Internet
Mathematical Models
Problem Solving
Issue Date2005
Citation
Proceedings - Annual Ieee Symposium On Foundations Of Computer Science, Focs, 2005, v. 2005, p. 83-100 How to Cite?
AbstractWe 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 Identifierhttp://hdl.handle.net/10722/92651
ISSN
References

 

DC FieldValueLanguage
dc.contributor.authorAbraham, Ien_HK
dc.contributor.authorBartal, Yen_HK
dc.contributor.authorChan, THHen_HK
dc.contributor.authorDhamdhere, Ken_HK
dc.contributor.authorGupta, Aen_HK
dc.contributor.authorKleinberg, Jen_HK
dc.contributor.authorNeiman, Oen_HK
dc.contributor.authorSlivkins, Aen_HK
dc.date.accessioned2010-09-17T10:53:04Z-
dc.date.available2010-09-17T10:53:04Z-
dc.date.issued2005en_HK
dc.identifier.citationProceedings - Annual Ieee Symposium On Foundations Of Computer Science, Focs, 2005, v. 2005, p. 83-100en_HK
dc.identifier.issn0272-5428en_HK
dc.identifier.urihttp://hdl.handle.net/10722/92651-
dc.description.abstractWe 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.languageengen_HK
dc.relation.ispartofProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCSen_HK
dc.subjectFinite Element Methoden_HK
dc.subjectGraph Theoryen_HK
dc.subjectInterneten_HK
dc.subjectMathematical Modelsen_HK
dc.subjectProblem Solvingen_HK
dc.titleMetric embeddings with relaxed guaranteesen_HK
dc.typeConference_Paperen_HK
dc.identifier.emailChan, THH:hubert@cs.hku.hken_HK
dc.identifier.authorityChan, THH=rp01312en_HK
dc.description.naturelink_to_subscribed_fulltext-
dc.identifier.doi10.1109/SFCS.2005.51en_HK
dc.identifier.scopuseid_2-s2.0-33748589199en_HK
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-33748589199&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.volume2005en_HK
dc.identifier.spage83en_HK
dc.identifier.epage100en_HK
dc.identifier.scopusauthoridAbraham, I=7102212547en_HK
dc.identifier.scopusauthoridBartal, Y=7006542888en_HK
dc.identifier.scopusauthoridChan, THH=12645073600en_HK
dc.identifier.scopusauthoridDhamdhere, K=8593470600en_HK
dc.identifier.scopusauthoridGupta, A=8354044800en_HK
dc.identifier.scopusauthoridKleinberg, J=7005755823en_HK
dc.identifier.scopusauthoridNeiman, O=14525717700en_HK
dc.identifier.scopusauthoridSlivkins, A=8407870700en_HK
dc.identifier.citeulike3081677-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats