Euclidean distortion and the sparsest cut

Arora, Sanjeev¹ ; Lee, James² ; Naor, Assaf³

¹ Department of Computer Science, Princeton University, 356 Olden Street, Princeton, New Jersey 08544-2087
² Department of Mathematics, University of Washington, Seattle, Washington 98195
³ Courant Institute of Mathematical Sciences, New York University, Warren Weaver Hall 1305, 251 Mercer Street, New York, New York 10012

Journal of the American Mathematical Society, Tome 21 (2008) no. 1, pp. 1-21

Résumé

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

Détail

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

Bibliographie

[1] Achlioptas, Dimitris Database-friendly random projections: Johnson-Lindenstrauss with binary coins J. Comput. System Sci. 2003 671 687

[2] Klein, Philip, Agrawal, Ajit, Ravi, R., Rao, Satish Approximation through multicommodity flow 1990 726 737

[3] Arora, Sanjeev, Rao, Satish, Vazirani, Umesh Expander flows, geometric embeddings and graph partitioning 2004 222 231

[4] Aumann, Yonatan, Rabani, Yuval An 𝑂(log𝑘) approximate min-cut max-flow theorem and approximation algorithm SIAM J. Comput. 1998 291 301

[5] Bartal, Yair Probabilistic approximation of metric spaces and its algorithmic applications 1996 184 193

[6] Bourgain, J. On Lipschitz embedding of finite metric spaces in Hilbert space Israel J. Math. 1985 46 52

[7] Calinescu, Gruia, Karloff, Howard, Rabani, Yuval Approximation algorithms for the 0-extension problem 2001 8 16

[8] Deza, Michel Marie, Laurent, Monique Geometry of cuts and metrics 1997

[9] Enflo, Per On the nonexistence of uniform homeomorphisms between 𝐿_{𝑝}-spaces Ark. Mat. 1969 103 105

[10] Fakcharoenphol, Jittat, Rao, Satish, Talwar, Kunal A tight bound on approximating arbitrary metrics by tree metrics 2003 448 455

[11] Figiel, T., Lindenstrauss, J., Milman, V. D. The dimension of almost spherical sections of convex bodies Acta Math. 1977 53 94

[12] Goemans, Michel X. Semidefinite programming in combinatorial optimization Math. Programming 1997 143 161

[13] Grã¶Tschel, M., Lovã¡Sz, L., Schrijver, A. The ellipsoid method and its consequences in combinatorial optimization Combinatorica 1981 169 197

[14] Heinonen, Juha Lectures on analysis on metric spaces 2001

[15] Johnson, William B., Lindenstrauss, Joram Extensions of Lipschitz mappings into a Hilbert space 1984 189 206

[16] Krauthgamer, R., Lee, J. R., Mendel, M., Naor, A. Measured descent: a new embedding method for finite metrics Geom. Funct. Anal. 2005 839 858

[17] Lee, James R., Mendel, Manor, Naor, Assaf Metric structures in 𝐿₁: dimension, snowflakes, and average distortion European J. Combin. 2005 1180 1190

[18] Lee, J. R., Naor, A. Embedding the diamond graph in 𝐿_{𝑝} and dimension reduction in 𝐿₁ Geom. Funct. Anal. 2004 745 747

[19] Lee, James R., Naor, Assaf Extending Lipschitz functions via random metric partitions Invent. Math. 2005 59 95

[20] Leighton, Tom, Rao, Satish Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms J. ACM 1999 787 832

[21] Linial, Nathan, London, Eran, Rabinovich, Yuri The geometry of graphs and some of its algorithmic applications Combinatorica 1995 215 245

[22] Linial, Nathan, Saks, Michael Low diameter graph decompositions Combinatorica 1993 441 454

[23] Matouå¡Ek, Jiå™Ã­ Lectures on discrete geometry 2002

[24] Shahrokhi, Farhad, Matula, D. W. The maximum concurrent flow problem J. Assoc. Comput. Mach. 1990 318 334

[25] Mendel, Manor, Naor, Assaf Euclidean quotients of finite metric spaces Adv. Math. 2004 451 494

[26] Milman, Vitali D., Schechtman, Gideon Asymptotic theory of finite-dimensional normed spaces 1986

[27] Naor, Assaf, Peres, Yuval, Schramm, Oded, Sheffield, Scott Markov chains in smooth Banach spaces and Gromov-hyperbolic metric spaces Duke Math. J. 2006 165 197

[28] Naor, Assaf, Rabani, Yuval, Sinclair, Alistair Quasisymmetric embeddings, the observable diameter, and expansion properties of graphs J. Funct. Anal. 2005 273 303

[29] Naor, Assaf, Schechtman, Gideon Remarks on non linear type and Pisier’s inequality J. Reine Angew. Math. 2002 213 236

[30] Rao, Satish Small distortion and volume preserving embeddings for planar and Euclidean metrics 1999 300 306

[31] Vazirani, Vijay V. Approximation algorithms 2001