Embeddings of Negative-type Metrics and An Improved Approximation to Generalized Sparsest Cut

In this paper, we study the metrics of negative type, which are metrics (V, d) such that √d is an Euclidean metric; these metrics are thus also known as "l2-squared" metrics.We show how to embed n-point negative-type metrics into Euclidean space l2 with distortion D = O(log3/4 n). This embedding result, in turn, implies an O(log3/4 k)-approximation algorithm for the Sparsest Cut problem with non-uniform demands. Another corollary we obtain is that n-point subsets of l1 embed into l2 with distortion O(log3/4 n).