File Download
  Links for fulltext
     (May Require Subscription)
Supplementary

Article: Metric embeddings with relaxed guarantees

TitleMetric embeddings with relaxed guarantees
Authors
KeywordsLow-distortion embeddings
Metric decompositions
Metric embeddings
Metric spaces
Randomized algorithms
Issue Date2009
PublisherSociety for Industrial and Applied Mathematics. The Journal's web site is located at http://epubs.siam.org/sam-bin/dbq/toclist/SICOMP
Citation
SIAM Journal On Computing, 2009, v. 38 n. 6, p. 2303-2329 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 [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 Identifierhttp://hdl.handle.net/10722/92628
ISSN
2015 Impact Factor: 0.841
2015 SCImago Journal Rankings: 1.808
ISI Accession Number ID
Funding AgencyGrant Number
Carnegie Mellon University
NSFITR CCR-0122581
CCF-0448095
CCF-0325453
IIS-0329064
CCR-0122381
Alfred P. Sloan Fellowship
Packard Fellowship of Jon Kleinberg
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 FieldValueLanguage
dc.contributor.authorChan, THHen_HK
dc.contributor.authorDhamdhere, Ken_HK
dc.contributor.authorGupta, Aen_HK
dc.contributor.authorKleinberg, Jen_HK
dc.contributor.authorSlivkins, Aen_HK
dc.date.accessioned2010-09-17T10:52:22Z-
dc.date.available2010-09-17T10:52:22Z-
dc.date.issued2009en_HK
dc.identifier.citationSIAM Journal On Computing, 2009, v. 38 n. 6, p. 2303-2329en_HK
dc.identifier.issn0097-5397en_HK
dc.identifier.urihttp://hdl.handle.net/10722/92628-
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 [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.languageengen_HK
dc.publisherSociety for Industrial and Applied Mathematics. The Journal's web site is located at http://epubs.siam.org/sam-bin/dbq/toclist/SICOMPen_HK
dc.relation.ispartofSIAM Journal on Computingen_HK
dc.rightsCreative Commons: Attribution 3.0 Hong Kong License-
dc.subjectLow-distortion embeddingsen_HK
dc.subjectMetric decompositionsen_HK
dc.subjectMetric embeddingsen_HK
dc.subjectMetric spacesen_HK
dc.subjectRandomized algorithmsen_HK
dc.titleMetric embeddings with relaxed guaranteesen_HK
dc.typeArticleen_HK
dc.identifier.emailChan, THH:hubert@cs.hku.hken_HK
dc.identifier.authorityChan, THH=rp01312en_HK
dc.description.naturepublished_or_final_version-
dc.identifier.doi10.1137/060670511en_HK
dc.identifier.scopuseid_2-s2.0-65949122721en_HK
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-65949122721&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.volume38en_HK
dc.identifier.issue6en_HK
dc.identifier.spage2303en_HK
dc.identifier.epage2329en_HK
dc.identifier.eissn1095-7111-
dc.identifier.isiWOS:000266018400008-
dc.publisher.placeUnited Statesen_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.scopusauthoridSlivkins, A=8407870700en_HK

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats