Euclidean distortion and the sparsest cut

We prove that every n-point metric space of negative type (in particular, every n-point subset of L 1 ) embeds into a Euclidean space with distortion O(√log n log log n), a result which is tight up to the O(log log n) 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, we achieve an approximation ratio of O(√log k log log k).

Authors

• Sanjeev Arora
• James R. Lee
• Assaf Naor

Keywords

• approximation algorithms
• metric embeddings
• semidefinite programming
• sparsest cut