Euclidean distortion and the Sparsest Cut
| dc.creator | Arora, Sanjeev | |
| dc.creator | Lee, James R. | |
| dc.creator | Naor, Assaf | |
| dc.date | 2005-08-08 | |
| dc.date.accessioned | 2026-07-07T05:22:16Z | |
| dc.date.available | 2026-07-07T05:22:16Z | |
| dc.description | We prove that every $n$-point metric space of negative type (and, in particular, every $n$-point subset of $L_1$) embeds into a Euclidean space with distortion $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. Namely, if the demand is supported on a subset of size $k$, we achieve an approximation ratio of $O(\sqrt{\log k}\cdot \log \log k)$. | |
| dc.description | 20 pages | |
| dc.identifier | https://arxiv.org/abs/math/0508154 | |
| dc.identifier | http://arxiv.org/abs/math/0508154 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/75996 | |
| dc.subject | Metric Geometry | |
| dc.subject | 46B99; 68W25 | |
| dc.title | Euclidean distortion and the Sparsest Cut | |
| dc.type | text |