Embeddings of negative-type metrics and an improved approximation to generalized sparsest cut

ABSTRACT

In this article, we study metrics of negative type, which are metrics (V, d) such that &sqrt;d is an Euclidean metric; these metrics are thus also known as ℓ₂-squared metrics. We show how to embed n-point negative-type metrics into Euclidean space ℓ₂ with distortion D = O(log^3/4n). This embedding result, in turn, implies an O(log^3/4k)-approximation algorithm for the Sparsest Cut problem with nonuniform demands. Another corollary we obtain is that n-point subsets of ℓ₁ embed into ℓ₂ with distortion O(log^3/4 n).

REFERENCES

• 1: Sanjeev Arora , James R. Lee , Assaf Naor, Euclidean distortion and the sparsest cut, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060673]
• 2: 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]
• 3: 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]
• 4: Yair Bartal, On approximating arbitrary metrices by tree metrics, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.161-168, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276725]
• 5: Bourgain, J. 1985. On Lipschitz embeddings of finite metric spaces in Hilbert space. Israel J. Math. 52, 1-2, 46--52.
• 6: Gruia Calinescu , Howard Karloff , Yuval Rabani, Approximation Algorithms for the 0-Extension Problem, SIAM Journal on Computing, v.34 n.2, p.358-372, 2005 [doi>10.1137/S0097539701395978]
• 7: Shuchi Chawla , Robert Krauthgamer , Ravi Kumar , Yuval Rabani , D. Sivakumar, ON THE HARDNESS OF APPROXIMATING MULTICUT AND SPARSEST-CUT, Computational Complexity, v.15 n.2, p.94-114, June 2006 [doi>10.1007/s00037-006-0210-9]
• 8: Chandra Chekuri , Anupam Gupta , Ilan Newman , Yuri Rabinovich , Alistair Sinclair, Embedding k-Outerplanar Graphs into l₁, SIAM Journal on Discrete Mathematics, v.20 n.1, p.119-136, 2006 [doi>10.1137/S0895480102417379]
• 9: Kenneth L. Clarkson, Las Vegas algorithms for linear and integer programming when the dimension is small, Journal of the ACM (JACM), v.42 n.2, p.488-499, March 1995 [doi>10.1145/201019.201036]
• 10: Deza, M. M. and Laurent, M. 1997. Geometry of Cuts and Metrics. Algorithms and Combinatorics, vol. 15. Springer-Verlag, Berlin, Germany.
• 11: Enflo, P. 1969. On the nonexistence of uniform homeomorphisms between L _p-spaces. Arkiv För Matematik 8, 103--105.
• 12: Jittat Fakcharoenphol , Satish Rao , Kunal Talwar, A tight bound on approximating arbitrary metrics by tree metrics, Journal of Computer and System Sciences, v.69 n.3, p.485-497, November 2004 [doi>10.1016/j.jcss.2004.04.011]
• 13: Michel X. Goemans, Semidefinite programming in combinatorial optimization, Mathematical Programming: Series A and B, v.79 n.1-3, p.143-161, Oct. 1, 1997 [doi>10.1007/BF02614315]
• 14: Anupam Gupta , Robert Krauthgamer , James R. Lee, Bounded Geometries, Fractals, and Low-Distortion Embeddings, Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, p.534, October 11-14, 2003
• 15: Anupam Gupta , Ilan Newman , Yuri Rabinovich , Alistair Sinclair, Cuts, Trees and ℓ₁-Embeddings of Graphs*, Combinatorica, v.24 n.2, p.233-269, April 2004 [doi>10.1007/s00493-004-0015-x]
• 16: P. Indyk, Algorithmic Applications of Low-Distortion Geometric Embeddings, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.10, October 14-17, 2001
• 17: Karzanov, A. V. 1985. Metrics and undirected cuts. Math. Program. 32, 2, 183--198.
• 18: Subhash Khot, On the power of unique 2-prover 1-round games, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.510017]
• 19: Subhash A. Khot , Nisheeth K. Vishnoi, The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative Type Metrics into \ell 1, Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, p.53-62, October 23-25, 2005 [doi>10.1109/SFCS.2005.74]
• 20: Krauthgamer, R., Lee, J., Mendel, M., and Naor, A. 2005. Measured descent: A new embedding method for finite metrics. Geom. Funct. Anal. 15, 4, 839--858.
• 21: Robert Krauthgamer , Yuval Rabani, Improved lower bounds for embeddings into L₁, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.1010-1017, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109669]
• 22: 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
• 23: Lee, J. R. and Naor, A. 2005. Extending lipschitz functions via random metric partitions. Inventiones Mathematicae 160, 1, 59--95.
• 24: Tom Leighton , Satish Rao, Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms, Journal of the ACM (JACM), v.46 n.6, p.787-832, Nov. 1999 [doi>10.1145/331524.331526]
• 25: Linial, N. 2002. Finite metric-spaces --combinatorics, geometry and algorithms. In Proceedings of the International Congress of Mathematicians Vol. III. Higher Education Press, Beijing, China, 573--586.
• 26: Linial, N., London, E., and Rabinovich, Y. 1995. The geometry of graphs and some of its algorithmic applications. Combinatorica 15, 2, 215--245.
• 27: Nick Littlestone , Manfred K. Warmuth, The weighted majority algorithm, Information and Computation, v.108 n.2, p.212-261, Feb. 1, 1994 [doi>10.1006/inco.1994.1009]
• 28: Matoušek, J. 1999. On embedding trees into uniformly convex Banach spaces. Israel J. Math. 114, 221--237.
• 29: Jiri Matousek, Lectures on Discrete Geometry, Springer-Verlag New York, Inc., Secaucus, NJ, 2002
• 30: Matoušek, J. 1996. On the distortion required for embedding finite metric spaces into normed spaces. Israel J. Math. 93, 333--344.
• 31: Yuri Rabinovich, On average distortion of embedding metrics into the line and into L₁, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780609]
• 32: 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]
• 33: Farhad Shahrokhi , D. W. Matula, The maximum concurrent flow problem, Journal of the ACM (JACM), v.37 n.2, p.318-334, April 1990 [doi>10.1145/77600.77620]
• 34: David B. Shmoys, Cut problems and their application to divide-and-conquer, Approximation algorithms for NP-hard problems, PWS Publishing Co., Boston, MA, 1996
• 35: Welzl, E. 1996. Suchen und Konstruieren durch Verdoppeln. In Highlights der Informatik, I. Wegener, Ed. Springer, Berlin, Germany, 221--228.

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 algorithm, embedding, metrics, negative-type metric, sparsest cut