Euclidean distortion and the sparsest cut

ABSTRACT

We prove that every n-point metric space of negative type (in particular, every n-point subset of L1) embeds into a Euclidean space with distortion O(√log n log log n), a result which is tight up to the O(log log n) 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(√log k log log k).

REFERENCES

• 1: Dimitris Achlioptas, Database-friendly random projections: Johnson-Lindenstrauss with binary coins, Journal of Computer and System Sciences, v.66 n.4, p.671-687, 1 June 2003 [doi>10.1016/S0022-0000(03)00025-4]
• 2: Sanjeev Arora , Elad Hazan , Satyen Kale, 0(\sqrt {\log n)} Approximation to SPARSEST CUT in Õ(n²) Time, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04), p.238-247, October 17-19, 2004 [doi>10.1109/FOCS.2004.1]
• 3: Sanjeev Arora , Satish Rao , Umesh Vazirani, Expander flows, geometric embeddings and graph partitioning, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, p.222-231, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007355]
• 4: Yonatan Aumann , Yuval Rabani, An O(log k) Approximate Min-Cut Max-Flow Theorem and Approximation Algorithm, SIAM Journal on Computing, v.27 n.1, p.291-301, Feb. 1998 [doi>10.1137/S0097539794285983]
• 5: Y. Bartal, Probabilistic approximation of metric spaces and its algorithmic applications, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.184, October 14-16, 1996
• 6: J. Bourgain. On Lipschitz embedding of finite metric spaces in Hilbert space. Israel J. Math., 52(1-2):46--52, 1985.
• 7: Bo Brinkman , Moses Charikar, On the Impossibility of Dimension Reduction in \ell _1, Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, p.514, October 11-14, 2003
• 8: Shuchi Chawla , Anupam Gupta , Harald Räcke, Embeddings of negative-type metrics and an improved approximation to generalized sparsest cut, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 9: S. Chawla, R. Krauthgamer, R. Kumar, Y. Rabani, and D. Sivakumar. On embeddability of negative type metrics into l1. Manuscript, 2004.
• 10: P. Enflo. On the nonexistence of uniform homeomorphisms between L sbp-spaces. Ark. Mat., 8:103--105, 1969.
• 11: Jittat Fakcharoenphol , Satish Rao , Kunal Talwar, A tight bound on approximating arbitrary metrics by tree metrics, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780608]
• 12: T. Figiel, J. Lindenstrauss, and V. D. Milman. The dimension of almost spherical sections of convex bodies. Acta Math., 139(1-2):53--94, 1977.
• 13: J. Heinonen. Lectures on analysis on metric spaces. Universitext. Springer-Verlag, New York, 2001.
• 14: W. B. Johnson and J. Lindenstrauss. Extensions of Lipschitz mappings into a Hilbert space. In Conference in modern analysis and probability (New Haven, Conn., 1982), pages 189--206. Amer. Math. Soc., Providence, RI, 1984.
• 15: S. Khot and N. Vishnoi. On embeddability of negative type metrics into l1. Manuscript, 2004.
• 16: R. Krauthgamer, J. R. Lee, M. Mendel, and A. Naor. Measured descent: A new embedding method for finite metrics. Geom. Funct. Anal., 2004. To appear.
• 17: James R. Lee, On distance scales, embeddings, and efficient relaxations of the cut cone, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 18: J. R. Lee, M. Mendel, and A. Naor. Metric structures in L1: Dimension, snowflakes, and average distortion. European J. Combin., 2004. To appear.
• 19: J. R. Lee and A. Naor. Embedding the diamond graph in Lp and dimension reduction in L1. Geom. Funct. Anal., 14(4):745--747, 2004.
• 20: N. Linial, E. London, and Y. Rabinovich. The geometry of graphs and some of its algorithmic applications. Combinatorica, 15(2):215--245, 1995.
• 21: N. Linial and M. Saks. Low diameter graph decompositions. Combinatorica, 13(4):441--454, 1993.
• 22: Jiri Matousek, Lectures on Discrete Geometry, Springer-Verlag New York, Inc., Secaucus, NJ, 2002
• 23: M. Mendel and A. Naor. Euclidean quotients of finite metric spaces. Adv. Math., 189(2):451--494, 2004.
• 24: Vitali D Milman , Gideon Schechtman, Asymptotic theory of finite dimensional normed spaces, Springer-Verlag New York, Inc., New York, NY, 1986
• 25: A. Naor, Y. Peres, O. Schramm, and S. Sheffield. Markov chains in smooth normed spaces and Gromov hyperbolic metric spaces. Preprint, 2004.
• 26: A. Naor, Y. Rabani, and A. Sinclair. Quasisymmetric embeddings, the observable diameter, and expansion properties of graphs. Preprint, 2004.
• 27: A. Naor and G. Schechtman. Remarks on non linear type and Pisier's inequality. J. Reine Angew. Math., 552:213--236, 2002.
• 28: Satish Rao, Small distortion and volume preserving embeddings for planar and Euclidean metrics, Proceedings of the fifteenth annual symposium on Computational geometry, p.300-306, June 13-16, 1999, Miami Beach, Florida, United States [doi>10.1145/304893.304983]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.0 General

General Terms:
Algorithms, Theory

Keywords:
approximation algorithms, metric embeddings, semidefinite programming, sparsest cut