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