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

45th Annual Syposium on Foundations of Computer Science

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

Proceedings of the 44th Annual IEEE Conference on Foundations of Computer Science

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

Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms

Proceedings of the 20th Annual IEEE Conference on Computational Complexity

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

Proceedings of the 46th Annual IEEE Conference on Foundations of Computer Science

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

Proceedings of the 17th annual ACM-SIAM symposium on Discrete algorithm

Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms

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

Approximation Algorithms for NP-hard Problems (D.S. Hochbaum, ed.)

Vijay V. Vazirani, Approximation algorithms, Springer-Verlag, Berlin, 2001. MR 1851303