Euclidean distortion and the sparsest cut
HTML articles powered by AMS MathViewer
- by Sanjeev Arora, James R. Lee and Assaf Naor
- J. Amer. Math. Soc. 21 (2008), 1-21
- DOI: https://doi.org/10.1090/S0894-0347-07-00573-5
- Published electronically: August 9, 2007
- PDF | 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 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.
- 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 Proceedings of the 44th Annual IEEE Conference on Foundations of Computer Science, pages 514–523, 2003.
- 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 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.
- 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 Proceedings of the 46th Annual IEEE Conference on Foundations of Computer Science, pages 53–62, 2005.
- 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 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.
- 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 Approximation Algorithms for NP-hard Problems (D.S. Hochbaum, ed.), pages 192–235. PWS, 1997.
- Vijay V. Vazirani, Approximation algorithms, Springer-Verlag, Berlin, 2001. MR 1851303
Bibliographic 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