Euclidean distortion and the sparsest cut

Arora, Sanjeev; Lee, James; Naor, Assaf

doi:10.1090/S0894-0347-07-00573-5

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 -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. 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, https://doi.org/10.1016/S0022-0000(03)00025-4
2. 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, https://doi.org/10.1109/FSCS.1990.89595
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. 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, https://doi.org/10.1145/1007352.1007355
6. Yonatan Aumann and Yuval Rabani, An 𝑂(log𝑘) approximate min-cut max-flow theorem and approximation algorithm, SIAM J. Comput. 27 (1998), no. 1, 291–301. MR 1614825, https://doi.org/10.1137/S0097539794285983
7. 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, https://doi.org/10.1109/SFCS.1996.548477
8. J. Bourgain, On Lipschitz embedding of finite metric spaces in Hilbert space, Israel J. Math. 52 (1985), no. 1-2, 46–52. MR 815600, https://doi.org/10.1007/BF02776078
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. 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
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. Michel Marie Deza and Monique Laurent, Geometry of cuts and metrics, Algorithms and Combinatorics, vol. 15, Springer-Verlag, Berlin, 1997. MR 1460488
14. Per Enflo, On the nonexistence of uniform homeomorphisms between 𝐿_{𝑝}-spaces, Ark. Mat. 8 (1969), 103–105. MR 271719, https://doi.org/10.1007/BF02589549
15. 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, https://doi.org/10.1145/780542.780608
16. 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, https://doi.org/10.1007/BF02392234
17. 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, https://doi.org/10.1016/S0025-5610(97)00051-8
18. 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, https://doi.org/10.1007/BF02579273
19. Juha Heinonen, Lectures on analysis on metric spaces, Universitext, Springer-Verlag, New York, 2001. MR 1800917
20. 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, https://doi.org/10.1090/conm/026/737400
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 (2005), no. 4, 839–858. MR 2221152, https://doi.org/10.1007/s00039-005-0527-6
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. James R. Lee, Manor Mendel, and Assaf Naor, Metric structures in 𝐿₁: dimension, snowflakes, and average distortion, European J. Combin. 26 (2005), no. 8, 1180–1190. MR 2163751, https://doi.org/10.1016/j.ejc.2004.07.002
26. J. R. Lee and A. Naor, Embedding the diamond graph in 𝐿_{𝑝} and dimension reduction in 𝐿₁, Geom. Funct. Anal. 14 (2004), no. 4, 745–747. MR 2084978, https://doi.org/10.1007/s00039-004-0473-8
27. James R. Lee and Assaf Naor, Extending Lipschitz functions via random metric partitions, Invent. Math. 160 (2005), no. 1, 59–95. MR 2129708, https://doi.org/10.1007/s00222-004-0400-5
28. 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, https://doi.org/10.1145/331524.331526
29. 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, https://doi.org/10.1007/BF01200757
30. Nathan Linial and Michael Saks, Low diameter graph decompositions, Combinatorica 13 (1993), no. 4, 441–454. MR 1262920, https://doi.org/10.1007/BF01303516
31. Jiří Matoušek, Lectures on discrete geometry, Graduate Texts in Mathematics, vol. 212, Springer-Verlag, New York, 2002. MR 1899299
32. Farhad Shahrokhi and D. W. Matula, The maximum concurrent flow problem, J. Assoc. Comput. Mach. 37 (1990), no. 2, 318–334. MR 1072261, https://doi.org/10.1145/77600.77620
33. Manor Mendel and Assaf Naor, Euclidean quotients of finite metric spaces, Adv. Math. 189 (2004), no. 2, 451–494. MR 2101227, https://doi.org/10.1016/j.aim.2003.12.001
34. 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
35. 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, https://doi.org/10.1215/S0012-7094-06-13415-4
36. 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, https://doi.org/10.1016/j.jfa.2005.04.003
37. Assaf Naor and Gideon Schechtman, Remarks on non linear type and Pisier’s inequality, J. Reine Angew. Math. 552 (2002), 213–236. MR 1940437, https://doi.org/10.1515/crll.2002.092
38. 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, https://doi.org/10.1145/304893.304983
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. Vijay V. Vazirani, Approximation algorithms, Springer-Verlag, Berlin, 2001. MR 1851303