loading...
Local Global Tradeoffs in Metric Embeddings
Providence, Rhode Island October 21-October 23
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/FOCS.2007.6448th Annual IEEE Symposium on Foundat ...
 This Article 
 
PDF
HTML
 
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
Suppose that every k points in a metric space X are D-distortion embeddable into \ell _1. We give upper and lower bounds on the distortion required to embed the entire space X into \ell _1. This is a natural mathematical question and is also motivated by the study of relaxations obtained by lift-and-project methods for graph partitioning problems. In this setting, we show that X can be embedded into \ell _1 with distortion {\rm O}(D \times \log (\left| X \right|/k)). Moreover, we give a lower bound showing that this result is tight if D is bounded away from 1. For D = 1 + \delta we give a lower bound of \Omega (\log (\left| X \right|/k)/\log (1/\delta )); and for D = 1, we give a lower bound of \Omega (\log \left| X \right|/(\log k + \log \log \left| X \right|)). Our bounds significantly improve on the results of Arora, Lovész, Newman, Rabani, Rabinovich and Vempala, who initiated a study of these questions.
Citation:
Moses Charikar, Konstantin Makarychev, Yury Makarychev, "Local Global Tradeoffs in Metric Embeddings," focs, pp.713-723, 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS'07), 2007
Usage of this product signifies your acceptance of the Terms of Use.


Suggestions