Skip to Main Content

Journal of the American Mathematical Society

Published by the American Mathematical Society, the Journal of the American Mathematical Society (JAMS) is devoted to research articles of the highest quality in all areas of pure and applied mathematics.

ISSN 1088-6834 (online) ISSN 0894-0347 (print)

The 2020 MCQ for Journal of the American Mathematical Society is 4.79.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.

 

Euclidean distortion and the sparsest cut
HTML articles powered by AMS MathViewer

by Sanjeev Arora, James R. Lee and Assaf Naor PDF
J. Amer. Math. Soc. 21 (2008), 1-21 Request permission

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
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
  • MR Author ID: 362095
  • Email: arora@cs.princeton.edu
  • James R. Lee
  • Affiliation: Department of Mathematics, University of Washington, Seattle, Washington 98195
  • Email: jrl@cs.washington.edu
  • Assaf Naor
  • Affiliation: Courant Institute of Mathematical Sciences, New York University, Warren Weaver Hall 1305, 251 Mercer Street, New York, New York 10012
  • Email: naor@cims.nyu.edu
  • 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.
  • © Copyright 2007 American Mathematical Society
  • Journal: J. Amer. Math. Soc. 21 (2008), 1-21
  • MSC (2000): Primary 51F99, 46B07, 68W25
  • DOI: https://doi.org/10.1090/S0894-0347-07-00573-5
  • MathSciNet review: 2350049