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
DOI:
https://doi.org/10.1090/S0894-0347-07-00573-5
Published electronically:
August 9, 2007
MathSciNet review:
2350049
Full-text PDF Free Access
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)$.
- 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 https://doi.org/10.1016/S0022-0000%2803%2900025-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 https://doi.org/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 https://doi.org/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 https://doi.org/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 https://doi.org/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 https://doi.org/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
- Per Enflo, On the nonexistence of uniform homeomorphisms between $L_{p}$-spaces, Ark. Mat. 8 (1969), 103–105. MR 271719, DOI https://doi.org/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 https://doi.org/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 https://doi.org/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 https://doi.org/10.1016/S0025-5610%2897%2900051-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 https://doi.org/10.1007/BF02579273
- Juha Heinonen, Lectures on analysis on metric spaces, Universitext, Springer-Verlag, New York, 2001. MR 1800917
- 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 https://doi.org/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 https://doi.org/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 https://doi.org/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 https://doi.org/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 https://doi.org/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 https://doi.org/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 https://doi.org/10.1007/BF01200757
- Nathan Linial and Michael Saks, Low diameter graph decompositions, Combinatorica 13 (1993), no. 4, 441–454. MR 1262920, DOI https://doi.org/10.1007/BF01303516
- Jiří Matoušek, Lectures on discrete geometry, Graduate Texts in Mathematics, vol. 212, Springer-Verlag, New York, 2002. MR 1899299
- Farhad Shahrokhi and D. W. Matula, The maximum concurrent flow problem, J. Assoc. Comput. Mach. 37 (1990), no. 2, 318–334. MR 1072261, DOI https://doi.org/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 https://doi.org/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 https://doi.org/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 https://doi.org/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 https://doi.org/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 https://doi.org/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
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
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