Remote Access Journal of the American Mathematical Society
Green Open Access

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

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

  • 1. D. Achlioptas.
    Database-friendly random projections: Johnson-Lindenstrauss with binary coins.
    J. Comput. System Sci., 66(4):671-687, 2003.
    Special issue on PODS 2001 (Santa Barbara, CA). MR 2005771 (2004h:68027)
  • 2. A. Agrawal, P. Klein, R. Ravi, and S. Rao.
    Approximation through multicommodity flow.
    In 31st Annual Symposium on Foundations of Computer Science, pages 726-737. IEEE Computer Soc., Los Alamitos, CA, 1990. MR 1150728 (92j:90031)
  • 3. S. Arora, E. Hazan, and S. Kale.
    $ {O}(\sqrt{\log n})$ approximation to SPARSEST CUT in $ \tilde{O}(n^2)$ time.
    In 45th Annual Syposium on Foundations of Computer Science, pages 238-247. IEEE Computer Society, 2004.
  • 4. S. Arora, J. R. Lee, and A. Naor.
    Fréchet embeddings of negative type metrics.
    Preprint, 2005.
  • 5. S. Arora, S. Rao, and U. Vazirani.
    Expander flows, geometric embeddings, and graph partitionings.
    In 36th Annual Symposium on the Theory of Computing, pages 222-231, 2004. MR 2121604 (2005j:68081)
  • 6. Y. Aumann and Y. Rabani.
    An $ O(\log k)$ approximate min-cut max-flow theorem and approximation algorithm.
    SIAM J. Comput., 27(1):291-301 (electronic), 1998. MR 1614825 (99d:05078)
  • 7. Y. Bartal.
    Probabilistic approximations of metric space and its algorithmic application.
    In 37th Annual Symposium on Foundations of Computer Science, pages 183-193, Oct. 1996. MR 1450616
  • 8. J. Bourgain.
    On Lipschitz embedding of finite metric spaces in Hilbert space.
    Israel J. Math., 52(1-2):46-52, 1985. MR 815600 (87b:46017)
  • 9. B. Brinkman and M. Charikar.
    On the impossibility of dimension reduction in $ \ell_1$.
    In Proceedings of the 44th Annual IEEE Conference on Foundations of Computer Science, pages 514-523, 2003.
  • 10. G. Calinescu, H. Karloff, and Y. Rabani.
    Approximation algorithms for the 0-extension problem.
    In Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 8-16, Philadelphia, PA, 2001. MR 1958386
  • 11. S. Chawla, A. Gupta, and H. Räcke.
    Embeddings of negative-type metrics and an improved approximation to generalized sparsest cut.
    In Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 102-111, Vancouver, 2005.
  • 12. S. Chawla, R. Krauthgamer, R. Kumar, Y. Rabani, and D. Sivakumar.
    On embeddability of negative type metrics into $ \ell_1$.
    In Proceedings of the 20th Annual IEEE Conference on Computational Complexity, pages 144-153, 2005.
  • 13. M. M. Deza and M. Laurent.
    Geometry of cuts and metrics, volume 15 of Algorithms and Combinatorics.
    Springer-Verlag, Berlin, 1997. MR 1460488 (98g:52001)
  • 14. P. Enflo.
    On the nonexistence of uniform homeomorphisms between $ {L}\sb{p}$-spaces.
    Ark. Mat., 8:103-105, 1969. MR 0271719 (42:6600)
  • 15. J. Fakcharoenphol, S. Rao, and K. Talwar.
    A tight bound on approximating arbitrary metrics by tree metrics.
    In Proceedings of the 35th Annual ACM Symposium on Theory of Computing, pages 448-455, 2003. MR 2120458 (2005j:68142)
  • 16. T. Figiel, J. Lindenstrauss, and V. D. Milman.
    The dimension of almost spherical sections of convex bodies.
    Acta Math., 139(1-2):53-94, 1977. MR 0445274 (56:3618)
  • 17. M. X. Goemans.
    Semidefinite programming and combinatorial optimization.
    Mathematical Programming, 49:143-161, 1997. MR 1464765 (98g:90028)
  • 18. M. Grötschel, L. L. Lovász, and A. Schrijver.
    The ellipsoid method and its consequences in combinatorial optimization.
    Combinatorica, 1:169-197, 1981. MR 625550 (84a:90044)
  • 19. J. Heinonen.
    Lectures on analysis on metric spaces.
    Universitext. Springer-Verlag, New York, 2001. MR 1800917 (2002c:30028)
  • 20. W. B. Johnson and J. Lindenstrauss.
    Extensions of Lipschitz mappings into a Hilbert space.
    In Conference in modern analysis and probability (New Haven, Conn., 1982), pages 189-206. Amer. Math. Soc., Providence, RI, 1984. MR 737400 (86a:46018)
  • 21. S. Khot and N. Vishnoi.
    The unique games conjecture, integrality gap for cut problems and embeddability of negative type metrics into $ \ell_1$.
    In Proceedings of the 46th Annual IEEE Conference on Foundations of Computer Science, pages 53-62, 2005.
  • 22. R. Krauthgamer, J. R. Lee, M. Mendel, and A. Naor.
    Measured descent: a new embedding method for finite metrics.
    Geom. Funct. Anal., 15(4):839-858, 2005. MR 2221152 (2007f:68249)
  • 23. R. Krauthgamer and Y. Rabani.
    Improved lower bounds for embeddings into $ l_1$.
    In Proceedings of the 17th annual ACM-SIAM symposium on Discrete algorithm, pages 1010-1017. ACM Press, 2006.
  • 24. J. R. Lee.
    On distance scales, embeddings, and efficient relaxations of the cut cone.
    In Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 92-101, Vancouver, 2005.
    Available at
  • 25. J. R. Lee, M. Mendel, and A. Naor.
    Metric structures in $ L\sb 1$: dimension, snowflakes, and average distortion.
    European J. Combin., 26(8):1180-1190, 2005. MR 2163751 (2006g:46012)
  • 26. J. R. Lee and A. Naor.
    Embedding the diamond graph in $ {L}_p$ and dimension reduction in $ {L}_1$.
    Geom. Funct. Anal., 14(4):745-747, 2004. MR 2084978 (2005g:46035)
  • 27. J. R. Lee and A. Naor.
    Extending Lipschitz functions via random metric partitions.
    Invent. Math., 160(1):59-95, 2005. MR 2129708 (2006c:54013)
  • 28. T. Leighton and S. Rao.
    Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms.
    J. ACM, 46(6):787-832, 1999. MR 1753034 (2001e:05125)
  • 29. N. Linial, E. London, and Y. Rabinovich.
    The geometry of graphs and some of its algorithmic applications.
    Combinatorica, 15(2):215-245, 1995. MR 1337355 (96e:05158)
  • 30. N. Linial and M. Saks.
    Low diameter graph decompositions.
    Combinatorica, 13(4):441-454, 1993. MR 1262920 (95d:05123)
  • 31. J. Matoušek.
    Lectures on discrete geometry, volume 212 of Graduate Texts in Mathematics.
    Springer-Verlag, New York, 2002. MR 1899299 (2003f:52011)
  • 32. D. W. Matula and F. Shahrokhi.
    The maximum concurrent flow problem.
    J. ACM, 37(2):318-334, 1990. MR 1072261 (91j:90029)
  • 33. M. Mendel and A. Naor.
    Euclidean quotients of finite metric spaces.
    Adv. Math., 189(2):451-494, 2004. MR 2101227 (2005h:54031)
  • 34. V. D. Milman and G. Schechtman.
    Asymptotic theory of finite-dimensional normed spaces, volume 1200 of Lecture Notes in Mathematics.
    Springer-Verlag, Berlin, 1986.
    With an appendix by M. Gromov. MR 856576 (87m:46038)
  • 35. A. Naor, Y. Peres, O. Schramm, and S. Sheffield.
    Markov chains in smooth Banach spaces and Gromov-hyperbolic metric spaces.
    Duke Math. J., 134(1):165-197, 2006. MR 2239346
  • 36. A. Naor, Y. Rabani, and A. Sinclair.
    Quasisymmetric embeddings, the observable diameter, and expansion properties of graphs.
    J. Funct. Anal., 227(2):273-303, 2005. MR 2168076 (2006j:68092)
  • 37. A. Naor and G. Schechtman.
    Remarks on non linear type and Pisier's inequality.
    J. Reine Angew. Math., 552:213-236, 2002. MR 1940437 (2003j:46010)
  • 38. S. Rao.
    Small distortion and volume preserving embeddings for planar and Euclidean metrics.
    In Proceedings of the 15th Annual Symposium on Computational Geometry, pages 300-306, New York, 1999. MR 1802217
  • 39. D. B. Shmoys.
    Cut problems and their application to divide-and-conquer.
    In Approximation Algorithms for NP-hard Problems (D.S. Hochbaum, ed.), pages 192-235. PWS, 1997.
  • 40. V. V. Vazirani.
    Approximation algorithms.
    Springer-Verlag, Berlin, 2001. MR 1851303 (2002h:68001)

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

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

American Mathematical Society