About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
FOCS 2007
Conference paper
Local global tradeoffs in metric embeddings
Abstract
Suppose that every k points in a metric space X are D-distortion embeddable into ℓ1. We give upper and lower bounds on the distortion required to embed the entire space X into ℓ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 ℓ1 with distortion O(D × log(|X|/k)). Moreover, we give a lower bound showing that this result is tight if D is bounded away from 1. For D = 1 + δ we give a lower bound of Ω(log(|X|/k)/ log(1/δ)); and for D = 1, we give a lower bound of Ω(log |X| / (log k+log log |X|)). Our bounds significantly improve on the results of Arora, Lovász, Newman, Rabani, Rabinovich and Vempala, who initiated a study of these questions. © 2007 IEEE.