On distance scales, embeddings, and efficient relaxations of the cut cone

ABSTRACT

A central open problem in the field of finite metric spaces is to find an efficient relaxation of the cut cone---the collection of positive linear combinations of cut pseudo-metrics on a finite set. In particular, it has been asked how well squared-Euclidean metrics (the so-called metrics of "negative type") embed into L1, and it is known that the answer to this question coincides with the integrality gap of a folklore semi-definite relaxation for computing the Sparsest Cut of a graph.Bourgain's classical embedding theorem implies that any n-point metric space embeds into L2 with O(log n) distortion. We give the first embeddings for metrics of negative type which beat Bourgain's bound. Specifically, we show that for every ∈ > 0, there exists a δ > 0 such that every n-point metric of negative type embeds into L2+∈, with distortion O(log n)^1-δ. We also exhibit the first o(log n) bounds on the Euclidean distortion of finite subsets of Lp, for 1 < p < 2. These spaces naturally interpolate between L1 and L2, and thus provide a necessary first step in resolving the long-standing open question on the Euclidean distortion of finite subsets of L1.In proving these results, we introduce a number of new techniques for the construction of low-distortion embeddings. These include a generic Gluing Lemma which avoids the overhead that typically arises from the naïve concatenation of different scales, and which provides new insights into the cut structure of finite graphs. We also exhibit the utility of Lipschitz extension theorems from Functional Analysis to the embedding of finite metric spaces. Finally, we prove the "Big Core" Theorem---a significantly improved and quantitatively optimal version of the main structural theorem in [ARV04] about random projections. The latter result offers a simplified hyperplane rounding algorithm for the computation of an O(√logn)-approximation to the Sparsest Cut problem with uniform demands.

REFERENCES

• 1: {ALN04} S. Arora, J. R. Lee, and A. Naor. Euclidean distortion and the Sparsest Cut. Manuscript, 2004.
• 2: 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]
• 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: {Ass83} Patrice Assouad. Plongements lipschitziens dans Rn. Bull. Soc. Math. France, 111(4):429--448, 1983.
• 5: 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]
• 6: {BL00} Yoav Benyamini and Joram Lindenstrauss. Geometric nonlinear functional analysis. Vol. 1, volume 48 of American Mathematical Society Colloquium Publications. American Mathematical Society, Providence, RI, 2000.
• 7: {Bou85} J. Bourgain. On Lipschitz embedding of finite metric spaces in Hilbert space. Israel J. Math., 52(1-2):46--52, 1985.
• 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: {Enf69} P. Enflo. On the nonexistence of uniform homeomorphisms between Lp-spaces. Ark. Mat., 8:103--105, 1969.
• 10: 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]
• 11: 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
• 12: Anupam Gupta , Alistair Sinclair , Ilan Newman , Yuri Rabinovich, Cuts, Trees and -Embeddings of Graphs, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.399, October 17-18, 1999
• 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: {KLMN04} R. Krauthgamer, J. R. Lee, M. Mendel, and A. Naor. Measured descent: A new embedding method for finite metrics. Submitted, 2004.
• 15: {Lin02} N. Linial. Squared l2 metrics into l1. In Open Problems, Workshop on Discrete Metric Spaces and their Algorithmic Applications. J. Matoušek, Ed., Haifa, 2002.
• 16: {LLR95} N. Linial, E. London, and Y. Rabinovich. The geometry of graphs and some of its algorithmic applications. Combinatorica, 15(2):215--245, 1995.
• 17: Jiri Matousek, Lectures on Discrete Geometry, Springer-Verlag New York, Inc., Secaucus, NJ, 2002
• 18: {MN04} M. Mendel and A. Naor. Euclidean quotients of finite metric spaces. To appear, Advances in Mathematics, 2004.
• 19: {MP84} M. B. Marcus and G. Pisier. Characterizations of almost surely continuous p-stable random Fourier series and strongly stationary processes. Acta Math., 152(3-4):245--301, 1984.
• 20: 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]
• 21: 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]
• 22: Vijay V. Vazirani, Approximation algorithms, Springer-Verlag New York, Inc., New York, NY, 2001