Euclidean distortion and the sparsest cut
Sanjeev Arora, James Lee, Assaf Naor · Journal of the American Mathematical Society · 2007
We prove that every n n -point metric space of negative type (and, in particular, every n n -point subset of L 1 L_1 ) embeds into a Euclidean space with distortion O ( log n ⋅ log log n ) O(\sqrt {\log n} \cdot \log \log n) , a result which is tight up to the iterated logarithm factor. As a consequence, we obtain the best known polynomial-time approximation algorithm for the Sparsest Cut problem with general demands. If the demand is supported on a subset of size k k , we achieve an approximation ratio of O ( log k ⋅ log log k ) O(\sqrt {\log k}\cdot \log \log k) .