On distance scales, embeddings, and efficient relaxations of the cut cone
James R. Lee · Symposium on Discrete Algorithms · 2005
A central open problem in the field of finite metric spaces is to find an efficient relaxation of the cut cone---the collection of positive linear combinations of cut pseudo-metrics on a finite set. In particular, it has been asked how well squared-Euclidean metrics (the so-called metrics of type) embed into L1, and it is known that the answer to this question coincides with the integrality gap of a folklore semi-definite relaxation for computing the Sparsest Cut of a graph.Bourgain's classical embedding theorem implies that any n-point metric space embeds into L2 with O(log n) distortion. We give the first embeddings for metrics of negative type which beat Bourgain's bound. Specifically, we show that for every ∈ > 0, there exists a δ > 0 such that every n-point metric of negative type embeds into L2+∈, with distortion O(log n)1-δ. We also exhibit the first o(log n) bounds on the Euclidean distortion of finite subsets of Lp, for 1