Journal of the American Mathematical Society

Author(s): Sanjeev Arora; James R. Lee; Assaf Naor
Journal: J. Amer. Math. Soc. 21 (2008), 1-21.
MSC (2000): Primary 51F99, 46B07, 68W25
Posted: August 9, 2007
Retrieve article in: PDF

Abstract: We prove that every

-point metric space of negative type (and, in particular, every

-point subset of

) 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

, we achieve an approximation ratio of $O(\sqrt{\log k}\cdot \log \log k)$ .

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 .
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 http://www.cs.washington.edu/homes/jrl/papers/soda05-full.pdf.
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)

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

Sanjeev Arora
Affiliation: Department of Computer Science, Princeton University, 356 Olden Street, Princeton, New Jersey 08544-2087
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

DOI: 10.1090/S0894-0347-07-00573-5
PII: S 0894-0347(07)00573-5
Keywords: Bi-Lipschitz embeddings, metrics of negative type, approximation algorithms.
Received by editor(s): August 8, 2005
Posted: 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 of article: Copyright 2007, American Mathematical Society

			Journals Home Search Author Info Subscribe Tech Support Help
ISSN: 1088-6834(e) ISSN: 0894-0347(p)

Previous issue \| Table of contents \| Next issue Articles in press \| Recently posted articles \| Most recent issue \| All issues Next Article


	Comments: webmaster@ams.org © Copyright 2009, American Mathematical Society Privacy Statement		Search the AMS