Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > LOW DISTORTION EMBEDDING:
Reports tagged with Low distortion embedding:
TR07-108 | 27th October 2007
Moses Charikar, Konstantin Makarychev, Yury Makarychev

Local Global Tradeoffs in Metric Embeddings

Suppose that every k points in a n point metric space X are D-distortion embeddable into l_1. We give upper and lower bounds on the distortion required to embed the entire space X into l_1. This is a natural mathematical question and is also motivated by the study of relaxations ... more >>>




ISSN 1433-8092 | Imprint