Authors: Sanjeev Arora , James R. Lee , Assaf Naor - ACM Symposium on Theory of Computing, STOC 2005 cited by 123
We prove that every n n -point metric space of negative type (and, in particular, every n n -point subset of L 1 L_1 ) embeds into a Euclidean space with distortion O ( log n ⋅ log log n ) 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 k , we achieve an approximation ratio of O ( log k ⋅ log log k ) O(\sqrt {\log k}\cdot \log \log k) .
✨ Checking sign-in… PDF Cited by View BibTeX Hide BibTeX View BibTeX Cite
On lipschitz embedding of finite metric spaces… On lipschitz embedding of finite metric spaces in Hilbert space Small Distortion and Volume Preserving… Small Distortion and Volume Preserving Embeddings for Planar and Euclidean Metrics Measured Descent: A New Embedding Method for… Measured Descent: A New Embedding Method for Finite Metrics Expander flows, geometric embeddings an… Expander flows, geometric embeddings and graph partitioning Extending Lipschitz functions via random… Extending Lipschitz functions via random metric partitions Metric structures in L1: dimension, snowflakes… Metric structures in L1: dimension, snowflakes, and average distortion Embeddings of negative-type metrics… Embeddings of negative-type metrics and an improved approximation to generalized sparsest cut The Unique Games Conjecture, Integrality… The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative Type Metrics into l1 On distance scales, embeddings, and… On distance scales, embeddings, and efficient relaxations of the cut cone Quasisymmetric embeddings, the… Quasisymmetric embeddings, the observable diameter, and expansion properties of graphs Improved lower bounds for embeddings into L1 Improved lower bounds for embeddings into L1 Fréchet Embeddings of Negative Type Metrics Fréchet Embeddings of Negative Type Metrics Expander flows, geometric embeddings an… Expander flows, geometric embeddings and graph partitioning Improved Approximation Algorithms for Minimum… Improved Approximation Algorithms for Minimum Weight Vertex Separators Fréchet Embeddings of Negative Type Metrics Fréchet Embeddings of Negative Type Metrics Vertex cuts, random walks, and dimension… Vertex cuts, random walks, and dimension reduction in series-parallel graphs A ( log n)^ Omega (1) integrality gap for the… A ( log n)^ Omega (1) integrality gap for the Sparsest Cut SDP Approximating Sparsest Cut in Graphs of Bounde… Approximating Sparsest Cut in Graphs of Bounded Treewidth Compression bounds for Lipschitz maps from the… Compression bounds for Lipschitz maps from the Heisenberg group to L1 L1 Embeddings of the Heisenberg Group and… L1 Embeddings of the Heisenberg Group and Fast Estimation of Graph Isoperimetry Near-optimal distortion bounds for embedding… Near-optimal distortion bounds for embedding doubling spaces into L1 Sparsest Cut on Bounded Treewidth Graphs… Sparsest Cut on Bounded Treewidth Graphs: Algorithms and Hardness Results The integrality gap of the Goemans-Linial SDP… The integrality gap of the Goemans-Linial SDP relaxation for Sparsest Cut is at least a constant multiple of √log n Vertical perimeter versus horizontal… Vertical perimeter versus horizontal perimeter Euclidean distortion and the sparsest cut Euclidean distortion and the sparsest cut Earlier references Focus paper Citing papers Older Newer Click a node to pin it, click the empty canvas to go back to this paper, or hover to preview. Open a node’s page from its title.
