Abstract: We prove that every -point metric space of negative type (and, in particular, every -point subset of ) embeds into a Euclidean space with distortion , 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. Namely, if the demand is supported on a subset of size , we achieve an approximation ratio of .
Recommendations
- Euclidean distortion and the sparsest cut (extended abstract)
- Embeddings of negative-type metrics and an improved approximation to generalized sparsest cut
- Embeddings of negative-type metrics and an improved approximation to generalized sparsest cut
- On distance scales, embeddings, and efficient relaxations of the cut cone
- Improved lower bounds for embeddings into \(L_1\)
Cites work
- \(O(\sqrt{\log n})\) approximation to sparsest cut in \(\tilde{O}(n^2)\) time
- A tight bound on approximating arbitrary metrics by tree metrics
- An O(log k) Approximate Min-Cut Max-Flow Theorem and Approximation Algorithm
- Applications of approximation algorithms to cooperative games
- Approximation algorithms for the 0-extension problem
- Asymptotic theory of finite dimensional normed spaces. With an appendix by M. Gromov: Isoperimetric inequalities in Riemannian manifolds
- Database-friendly random projections: Johnson-Lindenstrauss with binary coins.
- Embedding the diamond graph in L_p and dimension reduction in L₁
- Embeddings of negative-type metrics and an improved approximation to generalized sparsest cut
- Euclidean quotients of finite metric spaces
- Expander flows, geometric embeddings and graph partitioning
- Extending Lipschitz functions via random metric partitions
- Extensions of Lipschitz mappings into a Hilbert space
- Geometry of cuts and metrics
- scientific article; zbMATH DE number 1749054 (Why is no real title available?)
- Improved lower bounds for embeddings into L1
- Lectures on analysis on metric spaces
- Low diameter graph decompositions
- Markov chains in smooth Banach spaces and Gromov-hyperbolic metric spaces
- Measured descent: A new embedding method for finite metrics
- Metric structures in \(L_1\): dimension, snowflakes, and average distortion
- Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
- On distance scales, embeddings, and efficient relaxations of the cut cone
- On Lipschitz embedding of finite metric spaces in Hilbert space
- On the nonexistence of uniform homeomorphisms between \(L^ p\)-spaces
- Quasisymmetric embeddings, the observable diameter, and expansion properties of graphs
- Remarks on non linear type and Pisiers inequality
- Semidefinite programming in combinatorial optimization
- The dimension of almost spherical sections of convex bodies
- The ellipsoid method and its consequences in combinatorial optimization
- The geometry of graphs and some of its algorithmic applications
- The maximum concurrent flow problem
Cited in
(48)- Volume distortion for subsets of Euclidean spaces
- Vertical perimeter versus horizontal perimeter
- Quasimetric embeddings and their applications
- Sparsest cut in planar graphs, maximum concurrent flows and their connections with the max-cut problem
- An introduction to the Ribe program
- A 2-approximation for the bounded treewidth sparsest cut problem in \textsf{FPT} Time
- Terminal embeddings
- Fréchet embeddings of negative type metrics
- Negative-type diversities, a multi-dimensional analogue of negative-type metrics
- Mean isoperimetry with control on outliers: exact and approximation algorithms
- Convex relaxations and integrality gaps
- Book review of: M. I. Ostrovskii, Metric embeddings: Bilipschitz and coarse embedddings into Banach spaces
- Bilipschitz snowflakes and metrics of negative type
- On distance scales, embeddings, and efficient relaxations of the cut cone
- Embeddings of negative-type metrics and an improved approximation to generalized sparsest cut
- Optimal Euclidean Spanners
- Sparsest-cut in planar graphs, maximum concurrent flows and their connections with the max-cut problem
- Pythagorean powers of hypercubes
- Asymptotic negative type properties of finite ultrametric spaces
- The Andoni-Krauthgamer-Razenshteyn characterization of sketchable norms fails for sketchable metrics
- Euclidean distortion and the sparsest cut (extended abstract)
- Improved lower bounds for embeddings into \(L_1\)
- Compression bounds for Lipschitz maps from the Heisenberg group to \(L_{1}\)
- Vertical versus horizontal Poincaré inequalities on the Heisenberg group
- Lipschitz factorization through subsets of Hilbert space
- Embeddings of negative-type metrics and an improved approximation to generalized sparsest cut
- Approximating sparsest cut in low rank graphs via embeddings from approximately low-dimensional spaces
- On the structure of isometrically embeddable metric spaces
- Algorithms for metric learning via contrastive embeddings
- Diversity-normed spaces and diversity embeddings
- Algorithms for low-distortion embeddings into arbitrary 1-dimensional spaces
- Comparison of metric spectral gaps
- The unique games conjecture, integrality gap for cut problems and embeddability of negative-type metrics into _1
- On a class of metrics related to graph layout problems
- Least distortion Euclidean embeddings of flat tori
- Approximating Requirement Cut via a Configuration LP
- Proximinality and uniformly approximable sets in L^p
- Interactions of computational complexity theory and mathematics
- On the optimality of gluing over scales
- Moment inequalities for sums of random matrices and their applications in optimization
- A 2-approximation for the bounded treewidth sparsest cut problem in \textsf{FPT} time
- Beyond trees: the metric geometry of subsets of weighted Hamming cubes
- Approximating sparsest cut in low-treewidth graphs via combinatorial diameter
- When distances lie: Euclidean embeddings in the presence of outliers and distance violations
- Lipschitz decompositions of finite _p metrics
- Coarse differentiation and multi-flows in planar graphs
- Approximation algorithms for requirement cut on graphs
- The Euclidean distortion of the lamplighter group.
This page was built for publication: Euclidean distortion and the sparsest cut
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5423920)
