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.