Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS

Remote Access
Green Open Access
Journal of the American Mathematical Society
Journal of the American Mathematical Society
ISSN 1088-6834(online) ISSN 0894-0347(print)


Euclidean distortion and the sparsest cut

Authors: Sanjeev Arora, James R. Lee and Assaf Naor
Journal: J. Amer. Math. Soc. 21 (2008), 1-21
MSC (2000): Primary 51F99, 46B07, 68W25
Published electronically: August 9, 2007
MathSciNet review: 2350049
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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

References [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Journal of the American Mathematical Society with MSC (2000): 51F99, 46B07, 68W25

Retrieve articles in all journals with MSC (2000): 51F99, 46B07, 68W25

Additional Information

Sanjeev Arora
Affiliation: Department of Computer Science, Princeton University, 356 Olden Street, Princeton, New Jersey 08544-2087

James R. Lee
Affiliation: Department of Mathematics, University of Washington, Seattle, Washington 98195

Assaf Naor
Affiliation: Courant Institute of Mathematical Sciences, New York University, Warren Weaver Hall 1305, 251 Mercer Street, New York, New York 10012

PII: S 0894-0347(07)00573-5
Keywords: Bi-Lipschitz embeddings, metrics of negative type, approximation algorithms.
Received by editor(s): August 8, 2005
Published electronically: August 9, 2007
Additional Notes: The first author was supported by a David and Lucile Packard Fellowship and NSF grant CCR-0205594.
The second author was supported by NSF grant CCR-0121555 and an NSF Graduate Research Fellowship.
The last author was supported by NSF grants CCF-0635078 and DMS-0528387.
Article copyright: © Copyright 2007 American Mathematical Society