The geometry of graphs and some of its algorithmic applications

DOI10.1007/BF01200757zbMath0827.05021OpenAlexW2176446742WikidataQ105824835 ScholiaQ105824835MaRDI QIDQ1894703

Eran London, Yuri Rabinovich, Nathan Linial

Publication date: 24 July 1995

Published in: Combinatorica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01200757

zbMATH Keywords

algorithm decomposition embedding normed space multicommodity flow

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Special polytopes (linear programming, centrally symmetric, etc.) (52B12) Geometry and structure of normed linear spaces (46B20) Planar graphs; geometric and topological aspects of graph theory (05C10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Sketching and Embedding are Equivalent for Norms, Johnson–Lindenstrauss Embeddings with Kronecker Structure, Randomized numerical linear algebra: Foundations and algorithms, Metric Characterizations of Some Classes of Banach Spaces, Symmetric Graph Properties Have Independent Edges, The Range of Topological Effects on Communication, A smoothing majorization method for matrix minimization, How to Use Spanning Trees to Navigate in Graphs, A NOTE ON NON-AMENABILITY OF ℬ(ℓ_p) FOR p=1,2, Metric Embedding via Shortest Path Decompositions, Negative-type diversities, a multi-dimensional analogue of negative-type metrics, Lossless Prioritized Embeddings, Simplex Partitioning via Exponential Clocks and the Multiway-Cut Problem, Near isometric terminal embeddings for doubling metrics, Prioritized Metric Structures and Embedding, Proximity-preserving labeling schemes, Mean isoperimetry with control on outliers: exact and approximation algorithms, Diversity-normed spaces and diversity embeddings, On spatial conditioning of the spectrum of discrete random Schrödinger operators, Stochastic approximation of lamplighter metrics, Spectral dimension, Euclidean embeddings, and the metric growth exponent, Least distortion Euclidean embeddings of flat tori, Random Projection Ensemble Classification with High-Dimensional Time Series, Cut-sufficient directed 2-commodity multiflow topologies, Approximating spaces of Nagata dimension zero by weighted trees, Polynomial growth and asymptotic dimension, Labelings vs. embeddings: on distributed and prioritized representations of distances, Norms of structured random matrices, Lipschitz-free Spaces on Finite Metric Spaces, Diversities and the generalized circumradius, Unnamed Item, Expander graphs and their applications, Interactions of computational complexity theory and mathematics, Representation and coding of signal geometry, Network Essence: PageRank Completion and Centrality-Conforming Markov Chains, Unnamed Item, Unnamed Item, Single-Sink Multicommodity Flow with Side Constraints, Metric Curvatures Revisited: A Brief Overview, Euclidean distortion and the sparsest cut, Unnamed Item, Advances in metric embedding theory, Combinatorial theorems about embedding trees on the real line, On the equivalence between low-rank matrix completion and tensor rank, Comparison of Metric Spectral Gaps, Low Distortion Metric Embedding into Constant Dimension, A semidefinite bound for mixing rates of Markov chains, Approximating Requirement Cut via a Configuration LP, L ^p -distortion and p -spectral gap of finite graphs, The intrinsic dimensionality of graphs, On dominated $\ell_1$ metrics, On the dimension of trees, Spectral Techniques to Explore Point Clouds in Euclidean Space, with Applications to Collective Coordinates in Structural Biology, Unnamed Item, Inapproximability for metric embeddings into $\mathbb{R}^{d}$, A tight bound on approximating arbitrary metrics by tree metrics, Recovery of Low Rank Symmetric Matrices via Schatten p Norm Minimization, Hallucination Helps: Energy Efficient Virtual Circuit Routing, Book Review: Metric embeddings: bilipschitz and coarse embedddings into Banach spaces, Unnamed Item, Some applications of Ball’s extension theorem, Flip-flop spectrum-revealing QR factorization and its applications to singular value decomposition, Expanders with respect to Hadamard spaces and random graphs, Bandwidth and Low Dimensional Embedding, Optimal Lower Bounds for Universal and Differentially Private Steiner Trees and TSPs, Multicommodity flows and cuts in polymatroidal networks, Union of Euclidean Metric Spaces is Euclidean, DIAMOND GRAPHS AND SUPER-REFLEXIVITY, Compression functions of uniform embeddings of groups into Hilbert and Banach spaces, Simplex Transformations and the Multiway Cut Problem, On the Impossibility of Dimension Reduction for Doubling Subsets of $\ell_{p}$, A Splitting Augmented Lagrangian Method for Low Multilinear-Rank Tensor Recovery, The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative-Type Metrics into ℓ ₁, Approximation Algorithms for Low-Distortion Embeddings into Low-Dimensional Spaces, Near Isometric Terminal Embeddings for Doubling Metrics, The legacy of Jean Bourgain in geometric functional analysis, Truncated $l_{1-2}$ Models for Sparse Recovery and Rank Minimization, The geometry of crashes. A measure of the dynamics of stock market crises, Braess's paradox in expanders, On linear convergence of projected gradient method for a class of affine rank minimization problems, Reconstructing an economic space from a market metric, Geometric complexity of embeddings in $\mathbb R^d$, On the dilation spectrum of paths, cycles, and trees, A note on multiflows and treewidth, Metric violation distance: hardness and approximation, How to use spanning trees to navigate in graphs, Approximation and inapproximability results for maximum clique of disc graphs in high dimensions, Symmetric graph properties have independent edges, Topology-invariant similarity of nonrigid shapes, Coarse differentiation and multi-flows in planar graphs, Approximate $k$-Steiner forests via the Lagrangian relaxation technique with internal preprocessing, $\ell ^2_2$ spreading metrics for vertex ordering problems, Approximation algorithms for requirement cut on graphs, Limitations to Fréchet's metric embedding method, Vertical perimeter versus horizontal perimeter, An algorithmic theory of learning: robust concepts and random projection, Filament plots for data visualization, Semidefinite programming in combinatorial optimization, Phylogenetic placement problem: a hyperbolic embedding approach, On the distortion required for embedding finite metric spaces into normed spaces, Exact matrix completion via convex optimization, Theory of semidefinite programming for sensor network localization, Randomized nonlinear projections uncover high-dimensional structure, On embedding expanders into $\ell_p$ spaces, Exact low-rank matrix completion from sparsely corrupted entries via adaptive outlier pursuit, The modified accelerated Bregman method for regularized basis pursuit problem, Terminal embeddings, Towards duality of multicommodity multiroute cuts and flows: multilevel ball-growing, Metric differentiation, monotonicity and maps to $L^{1}$, Approximation of rank function and its application to the nearest low-rank correlation matrix, Bandwidth and low dimensional embedding, Generically globally rigid graphs have generic universally rigid frameworks, Lower bounds for the low-rank matrix approximation, Amenability, locally finite spaces, and bi-Lipschitz embeddings, An introduction to the Ribe program, Heat kernel embeddings, differential geometry and graph structure, Distance geometry and data science, The all-or-nothing flow problem in directed graphs with symmetric demand pairs, Space lower bounds for low-stretch greedy embeddings, Low-distortion embeddings of graphs with large girth, Database-friendly random projections: Johnson-Lindenstrauss with binary coins., Compression bounds for Lipschitz maps from the Heisenberg group to $L_{1}$, An approximation theory of matrix rank minimization and its application to quadratic equations, Null space conditions and thresholds for rank minimization, An implementable proximal point algorithmic framework for nuclear norm minimization, On the optimality of gluing over scales, Models and methods for solving the problem of network vulnerability, Diameters, distortion, and eigenvalues, Pathwidth, trees, and random embeddings, Tree metrics and edge-disjoint $S$-paths, On embedding trees into uniformly convex Banach spaces, Spanners in sparse graphs, Speed of random walks, isoperimetry and compression of finitely generated groups, A new approximation of the matrix rank function and its application to matrix rank minimization, Cut problems in graphs with a budget constraint, The non-linear geometry of Banach spaces after Nigel Kalton, On average distortion of embedding metrics into the line, Lipschitz factorization through subsets of Hilbert space, Optimal distortion embeddings of distance regular graphs into Euclidean spaces, Impossibility of almost extension, On orthogonal projections for dimension reduction and applications in augmented target loss functions for learning problems, Nonlinear spectral calculus and super-expanders, A new approach to low-distortion embeddings of finite metric spaces into non-superreflexive Banach spaces, Collective additive tree spanners of bounded tree-breadth graphs with generalizations and consequences, Fuzzy multilevel graph embedding, Convergence of fixed-point continuation algorithms for matrix rank minimization, Fixed point and Bregman iterative methods for matrix rank minimization, Nonembeddability theorems via Fourier analysis, The approximability of non-Boolean satisfiability problems and restricted integer programming, Meet and merge: approximation algorithms for confluent flows, Diffusion wavelets, An algorithmic theory of learning: Robust concepts and random projection, New algorithms for maximum disjoint paths based on tree-likeness, Constant distortion embeddings of symmetric diversities, Geometric component analysis and its applications to data analysis, Empire of colonies: Self-stabilizing and self-organizing distributed algorithm, Quasimetric embeddings and their applications, Impossibility of dimension reduction in the nuclear norm, A simple algorithm for the multiway cut problem, Characterizing the universal rigidity of generic frameworks, An average John theorem, A node-capacitated Okamura-Seymour theorem, Matrix optimization over low-rank spectral sets: stationary points and local and global minimizers, Sphere of influence graphs and the $L_{\infty}$-metric, Low distortion Euclidean embeddings of trees, Nonpositive curvature is not coarsely universal, An adaptation for iterative structured matrix completion, Truncated sparse approximation property and truncated $q$-norm minimization, Approximating the bandwidth via volume respecting embeddings, Metric structures in $L_1$: dimension, snowflakes, and average distortion, Quasi-semi-metrics, oriented multi-cuts and related polyhedra, Efficient algorithms for online decision problems, Light spanners for high dimensional norms via stochastic decompositions, Least-distortion Euclidean embeddings of graphs: Products of cycles and expanders, On dependent randomized rounding algorithms, Sensitivity of low-rank matrix recovery, The least Euclidean distortion constant of a distance-regular graph, On approximating planar metrics by tree metrics., Low dimensional embeddings of doubling metrics

Cites Work