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 obtained by lift-and-project methods for graph partitioning problems. In this setting, we show that X can be embedded into l(1) with distortion O( D x log(n/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(n/k)/ log(1/delta)); and for D = 1, we give a lower bound of Omega( log n/(log k + log logn)). Our bounds significantly improve on the results of Arora et al. who initiated a study of these questions.
metric embeddings global local properties lift and project