### Abstract

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).

Original language | English (US) |
---|---|

Pages (from-to) | 553-562 |

Number of pages | 10 |

Journal | Proceedings of the Annual ACM Symposium on Theory of Computing |

DOIs | |

State | Published - 2005 |

Event | 13th Color Imaging Conference: Color Science, Systems, Technologies, and Applications - Scottsdale, AZ, United States Duration: Nov 7 2005 → Nov 11 2005 |

### Keywords

- Approximation Algorithms
- Metric Embeddings
- Semidefinite Programming
- Sparsest Cut

### ASJC Scopus subject areas

- Software

## Fingerprint Dive into the research topics of 'Euclidean distortion and the Sparsest Cut'. Together they form a unique fingerprint.

## Cite this

Arora, S., Lee, J. R., & Naor, A. (2005). Euclidean distortion and the Sparsest Cut.

*Proceedings of the Annual ACM Symposium on Theory of Computing*, 553-562. https://doi.org/10.1145/1060590.1060673