## 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

- Dimitris Achlioptas,
*Database-friendly random projections: Johnson-Lindenstrauss with binary coins*, J. Comput. System Sci.**66**(2003), no. 4, 671–687. Special issue on PODS 2001 (Santa Barbara, CA). MR**2005771**, DOI 10.1016/S0022-0000(03)00025-4 - Philip Klein, Ajit Agrawal, R. Ravi, and Satish Rao,
*Approximation through multicommodity flow*, 31st Annual Symposium on Foundations of Computer Science, Vol. I, II (St. Louis, MO, 1990) IEEE Comput. Soc. Press, Los Alamitos, CA, 1990, pp. 726–737. MR**1150728**, DOI 10.1109/FSCS.1990.89595
AHK04 S. Arora, E. Hazan, and S. Kale. ${O}(\sqrt {\log n})$ approximation to SPARSEST CUT in $\tilde {O}(n^2)$ time. In - Sanjeev Arora, Satish Rao, and Umesh Vazirani,
*Expander flows, geometric embeddings and graph partitioning*, Proceedings of the 36th Annual ACM Symposium on Theory of Computing, ACM, New York, 2004, pp. 222–231. MR**2121604**, DOI 10.1145/1007352.1007355 - Yonatan Aumann and Yuval Rabani,
*An $O(\log k)$ approximate min-cut max-flow theorem and approximation algorithm*, SIAM J. Comput.**27**(1998), no. 1, 291–301. MR**1614825**, DOI 10.1137/S0097539794285983 - Yair Bartal,
*Probabilistic approximation of metric spaces and its algorithmic applications*, 37th Annual Symposium on Foundations of Computer Science (Burlington, VT, 1996) IEEE Comput. Soc. Press, Los Alamitos, CA, 1996, pp. 184–193. MR**1450616**, DOI 10.1109/SFCS.1996.548477 - J. Bourgain,
*On Lipschitz embedding of finite metric spaces in Hilbert space*, Israel J. Math.**52**(1985), no. 1-2, 46–52. MR**815600**, DOI 10.1007/BF02776078
BC03 B. Brinkman and M. Charikar. On the impossibility of dimension reduction in $\ell _1$. In - Gruia Calinescu, Howard Karloff, and Yuval Rabani,
*Approximation algorithms for the 0-extension problem*, Proceedings of the Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms (Washington, DC, 2001) SIAM, Philadelphia, PA, 2001, pp. 8–16. MR**1958386**
CGR04 S. Chawla, A. Gupta, and H. Räcke. Embeddings of negative-type metrics and an improved approximation to generalized sparsest cut. In - Michel Marie Deza and Monique Laurent,
*Geometry of cuts and metrics*, Algorithms and Combinatorics, vol. 15, Springer-Verlag, Berlin, 1997. MR**1460488**, DOI 10.1007/978-3-642-04295-9 - Per Enflo,
*On the nonexistence of uniform homeomorphisms between $L_{p}$-spaces*, Ark. Mat.**8**(1969), 103–105. MR**271719**, DOI 10.1007/BF02589549 - Jittat Fakcharoenphol, Satish Rao, and Kunal Talwar,
*A tight bound on approximating arbitrary metrics by tree metrics*, Proceedings of the Thirty-Fifth Annual ACM Symposium on Theory of Computing, ACM, New York, 2003, pp. 448–455. MR**2120458**, DOI 10.1145/780542.780608 - T. Figiel, J. Lindenstrauss, and V. D. Milman,
*The dimension of almost spherical sections of convex bodies*, Acta Math.**139**(1977), no. 1-2, 53–94. MR**445274**, DOI 10.1007/BF02392234 - Michel X. Goemans,
*Semidefinite programming in combinatorial optimization*, Math. Programming**79**(1997), no. 1-3, Ser. B, 143–161. Lectures on mathematical programming (ismp97) (Lausanne, 1997). MR**1464765**, DOI 10.1016/S0025-5610(97)00051-8 - M. Grötschel, L. Lovász, and A. Schrijver,
*The ellipsoid method and its consequences in combinatorial optimization*, Combinatorica**1**(1981), no. 2, 169–197. MR**625550**, DOI 10.1007/BF02579273 - Juha Heinonen,
*Lectures on analysis on metric spaces*, Universitext, Springer-Verlag, New York, 2001. MR**1800917**, DOI 10.1007/978-1-4613-0131-8 - William B. Johnson and Joram Lindenstrauss,
*Extensions of Lipschitz mappings into a Hilbert space*, Conference in modern analysis and probability (New Haven, Conn., 1982) Contemp. Math., vol. 26, Amer. Math. Soc., Providence, RI, 1984, pp. 189–206. MR**737400**, DOI 10.1090/conm/026/737400
KV04 S. Khot and N. Vishnoi. The unique games conjecture, integrality gap for cut problems and embeddability of negative type metrics into $\ell _1$. In - R. Krauthgamer, J. R. Lee, M. Mendel, and A. Naor,
*Measured descent: a new embedding method for finite metrics*, Geom. Funct. Anal.**15**(2005), no. 4, 839–858. MR**2221152**, DOI 10.1007/s00039-005-0527-6
KR06 R. Krauthgamer and Y. Rabani. Improved lower bounds for embeddings into $l_1$. In - James R. Lee, Manor Mendel, and Assaf Naor,
*Metric structures in $L_1$: dimension, snowflakes, and average distortion*, European J. Combin.**26**(2005), no. 8, 1180–1190. MR**2163751**, DOI 10.1016/j.ejc.2004.07.002 - J. R. Lee and A. Naor,
*Embedding the diamond graph in $L_p$ and dimension reduction in $L_1$*, Geom. Funct. Anal.**14**(2004), no. 4, 745–747. MR**2084978**, DOI 10.1007/s00039-004-0473-8 - James R. Lee and Assaf Naor,
*Extending Lipschitz functions via random metric partitions*, Invent. Math.**160**(2005), no. 1, 59–95. MR**2129708**, DOI 10.1007/s00222-004-0400-5 - Tom Leighton and Satish Rao,
*Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms*, J. ACM**46**(1999), no. 6, 787–832. MR**1753034**, DOI 10.1145/331524.331526 - Nathan Linial, Eran London, and Yuri Rabinovich,
*The geometry of graphs and some of its algorithmic applications*, Combinatorica**15**(1995), no. 2, 215–245. MR**1337355**, DOI 10.1007/BF01200757 - Nathan Linial and Michael Saks,
*Low diameter graph decompositions*, Combinatorica**13**(1993), no. 4, 441–454. MR**1262920**, DOI 10.1007/BF01303516 - Jiří Matoušek,
*Lectures on discrete geometry*, Graduate Texts in Mathematics, vol. 212, Springer-Verlag, New York, 2002. MR**1899299**, DOI 10.1007/978-1-4613-0039-7 - Farhad Shahrokhi and D. W. Matula,
*The maximum concurrent flow problem*, J. Assoc. Comput. Mach.**37**(1990), no. 2, 318–334. MR**1072261**, DOI 10.1145/77600.77620 - Manor Mendel and Assaf Naor,
*Euclidean quotients of finite metric spaces*, Adv. Math.**189**(2004), no. 2, 451–494. MR**2101227**, DOI 10.1016/j.aim.2003.12.001 - Vitali D. Milman and Gideon Schechtman,
*Asymptotic theory of finite-dimensional normed spaces*, Lecture Notes in Mathematics, vol. 1200, Springer-Verlag, Berlin, 1986. With an appendix by M. Gromov. MR**856576** - Assaf Naor, Yuval Peres, Oded Schramm, and Scott Sheffield,
*Markov chains in smooth Banach spaces and Gromov-hyperbolic metric spaces*, Duke Math. J.**134**(2006), no. 1, 165–197. MR**2239346**, DOI 10.1215/S0012-7094-06-13415-4 - Assaf Naor, Yuval Rabani, and Alistair Sinclair,
*Quasisymmetric embeddings, the observable diameter, and expansion properties of graphs*, J. Funct. Anal.**227**(2005), no. 2, 273–303. MR**2168076**, DOI 10.1016/j.jfa.2005.04.003 - Assaf Naor and Gideon Schechtman,
*Remarks on non linear type and Pisier’s inequality*, J. Reine Angew. Math.**552**(2002), 213–236. MR**1940437**, DOI 10.1515/crll.2002.092 - Satish Rao,
*Small distortion and volume preserving embeddings for planar and Euclidean metrics*, Proceedings of the Fifteenth Annual Symposium on Computational Geometry (Miami Beach, FL, 1999) ACM, New York, 1999, pp. 300–306. MR**1802217**, DOI 10.1145/304893.304983
Shmoys95 D. B. Shmoys. Cut problems and their application to divide-and-conquer. In - Vijay V. Vazirani,
*Approximation algorithms*, Springer-Verlag, Berlin, 2001. MR**1851303**

*45th Annual Syposium on Foundations of Computer Science*, pages 238–247. IEEE Computer Society, 2004. ALN-Frechet S. Arora, J. R. Lee, and A. Naor. Fréchet embeddings of negative type metrics. Preprint, 2005.

*Proceedings of the 44th Annual IEEE Conference on Foundations of Computer Science*, pages 514–523, 2003.

*Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms*, pages 102–111, Vancouver, 2005. SKKRS 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.

*Proceedings of the 46th Annual IEEE Conference on Foundations of Computer Science*, pages 53–62, 2005.

*Proceedings of the 17th annual ACM-SIAM symposium on Discrete algorithm*, pages 1010–1017. ACM Press, 2006. L04 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.

*Approximation Algorithms for NP-hard Problems (D.S. Hochbaum, ed.)*, pages 192–235. PWS, 1997.

## 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