Euclidean distortion and the sparsest cut

DOI10.1090/S0894-0347-07-00573-5zbMath1132.68070arXivmath/0508154MaRDI QIDQ5423920

James R. Lee, Assaf Naor, Sanjeev Arora

Publication date: 1 November 2007

Published in: Journal of the American Mathematical Society (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/math/0508154

zbMATH Keywords

approximation algorithmsbi-Lipschitz embeddingsmetrics of negative type

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Local theory of Banach spaces (46B07) Approximation algorithms (68W25)

Related Items

Coarse differentiation and multi-flows in planar graphs ⋮ Approximation algorithms for requirement cut on graphs ⋮ Vertical perimeter versus horizontal perimeter ⋮ 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 ⋮ A 2-approximation for the bounded treewidth sparsest cut problem in \textsf{FPT} Time ⋮ Negative-type diversities, a multi-dimensional analogue of negative-type metrics ⋮ Terminal embeddings ⋮ On a class of metrics related to graph layout problems ⋮ Mean isoperimetry with control on outliers: exact and approximation algorithms ⋮ Diversity-normed spaces and diversity embeddings ⋮ Least distortion Euclidean embeddings of flat tori ⋮ An introduction to the Ribe program ⋮ Proximinality and uniformly approximable sets in \(L^p\) ⋮ Compression bounds for Lipschitz maps from the Heisenberg group to \(L_{1}\) ⋮ Unnamed Item ⋮ 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 ⋮ Vertical versus horizontal Poincaré inequalities on the Heisenberg group ⋮ Lipschitz factorization through subsets of Hilbert space ⋮ On the Structure of Isometrically Embeddable Metric Spaces ⋮ Comparison of Metric Spectral Gaps ⋮ Fréchet embeddings of negative type metrics ⋮ Approximating Requirement Cut via a Configuration LP ⋮ The Euclidean distortion of the lamplighter group. ⋮ Unnamed Item ⋮ Convex Relaxations and Integrality Gaps ⋮ Quasimetric embeddings and their applications ⋮ Sparsest cut in planar graphs, maximum concurrent flows and their connections with the max-cut problem ⋮ Strong reductions for extended formulations ⋮ Book Review: Metric embeddings: bilipschitz and coarse embedddings into Banach spaces ⋮ Unnamed Item ⋮ The Andoni–Krauthgamer–Razenshteyn Characterization of Sketchable Norms Fails for Sketchable Metrics ⋮ Volume distortion for subsets of Euclidean spaces ⋮ Multicommodity flows and cuts in polymatroidal networks

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Asymptotic theory of finite dimensional normed spaces. With an appendix by M. Gromov: Isoperimetric inequalities in Riemannian manifolds
• On Lipschitz embedding of finite metric spaces in Hilbert space
• The ellipsoid method and its consequences in combinatorial optimization
• The dimension of almost spherical sections of convex bodies
• Low diameter graph decompositions
• Semidefinite programming in combinatorial optimization
• Database-friendly random projections: Johnson-Lindenstrauss with binary coins.
• Lectures on analysis on metric spaces
• Embedding the diamond graph in \(L_p\) and dimension reduction in \(L_1\)
• Euclidean quotients of finite metric spaces
• Extending Lipschitz functions via random metric partitions
• The geometry of graphs and some of its algorithmic applications
• Markov chains in smooth Banach spaces and Gromov-hyperbolic metric spaces
• On the nonexistence of uniform homeomorphisms between \(L^ p\)-spaces
• Metric structures in \(L_1\): dimension, snowflakes, and average distortion
• Measured descent: A new embedding method for finite metrics
• Quasisymmetric embeddings, the observable diameter, and expansion properties of graphs
• $O(\sqrt{\logn})$ Approximation to SPARSEST CUT in $\tilde{O}(n^2)$ Time
• Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
• Extensions of Lipschitz mappings into a Hilbert space
• The maximum concurrent flow problem
• Improved lower bounds for embeddings into L₁
• An O(log k) Approximate Min-Cut Max-Flow Theorem and Approximation Algorithm
• Remarks on non linear type and Pisiers inequality
• Applications of approximation algorithms to cooperative games
• Expander flows, geometric embeddings and graph partitioning
• A tight bound on approximating arbitrary metrics by tree metrics
• Geometry of cuts and metrics