Euclidean distortion and the Sparsest Cut

Details Euclidean distortion and the Sparsest Cut Euclidean distortion and the Sparsest Cut

2005-08-08

arxiv.org/abs/math/0508154v1

Mathematics

Metric Geometry

20 pages

Scientific paper

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

Affiliated with

Also associated with

No associations

Rating

Euclidean distortion and the Sparsest Cut does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Euclidean distortion and the Sparsest Cut, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Euclidean distortion and the Sparsest Cut will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-577013