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

ABSTRACT

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

REFERENCES

• 1: 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]
• 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: 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]
• 4: {Bou85} Jean Bourgain. On Lipschitz embeddings of nite metric spaces in Hilbert space. Israel Journal of Mathematics, 52(1-2):46--52, 1985.
• 5: {CGN+03} Chandra Chekuri, Anupam Gupta, Ilan Newman, Yuri Rabinovich, and Alistair Sinclair. Embedding k-outerplanar graphs into l1. In Proc. 14th SODA, pages 527--536, 2003.
• 6: 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]
• 7: {DL97} Michel Marie Deza and Monique Laurent. Geometry of cuts and metrics, volume 15 of Algorithms and Combinatorics. Springer-Verlag, Berlin, 1997.
• 8: 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]
• 9: 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
• 10: 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]
• 11: 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]
• 12: {Ind01} Piotr Indyk. Algorithmic aspects of geometric embeddings. In Proc. 42nd FOCS, pages 10--33, 2001.
• 13: {Kar85} Alexander V. Karzanov. Metrics and undirected cuts. Mathematical Programming, 32(2):183--198, 1985.
• 14: Robert Krauthgamer , James R. Lee , Manor Mendel , Assaf Naor, Measured Descent: A New Embedding Method for Finite Metrics, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04), p.434-443, October 17-19, 2004 [doi>10.1109/FOCS.2004.41]
• 15: 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
• 16: {Lin02} Nathan Linial. Finite metric-spaces---combinatorics, geometry and algorithms. In Proceedings of the International Congress of Mathematicians, Vol. III (Beijing, 2002), pages 573--586, Beijing, 2002. Higher Ed. Press.
• 17: {LLR95} Nathan Linial, Eran London, and Yuri Rabinovich. The geometry of graphs and some of its algorithmic applications. Combinatorica, 15(2):215--245, 1995. (Preliminary version in 35th FOCS, 1994).
• 18: {LN04} James Lee and Assaf Naor. Extending lipschitz functions via random metric partitions. Inventiones Mathematicae, 2004. To appear.
• 19: 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]
• 20: 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]
• 21: {Mat96} Jiří Matoušek. On the distortion required for embedding nite metric spaces into normed spaces. Israel Journal of Mathematics, 93:333--344, 1996.
• 22: {Mat99} Jiří Matoušek. On embedding trees into uniformly convex Banach spaces. Israel Journal of Mathematics, 114:221--237, 1999. (Czech version in : Lipschitz distance of metric spaces, C.Sc. degree thesis, Charles University, 1990).
• 23: Jiri Matousek, Lectures on Discrete Geometry, Springer-Verlag New York, Inc., Secaucus, NJ, 2002
• 24: 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]
• 25: 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]
• 26: David B. Shmoys, Cut problems and their application to divide-and-conquer, Approximation algorithms for NP-hard problems, PWS Publishing Co., Boston, MA, 1996
• 27: 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]
• 28: {Wel96} Emo Welzl. Suchen und Konstruieren durch Verdoppeln. In Ingo Wegener, editor, Highlights der Informatik, pages 221--228, Berlin, 1996. Springer.