Embeddings of negative-type metrics and an improved approximation to generalized sparsest cut

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