Expander flows, geometric embeddings and graph partitioning
From MaRDI portal
Publication:5899507
DOI10.1145/1502793.1502794zbMath1325.68255WikidataQ56503925 ScholiaQ56503925MaRDI QIDQ5899507
Satish B. Rao, Umesh V. Vazirani, Sanjeev Arora
Publication date: 11 November 2015
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/1502793.1502794
expansion; graph partitioning; multicommodity flows; expanders; semidefinite programs; graph separators
90C22: Semidefinite programming
90B10: Deterministic network models in operations research
05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C85: Graph algorithms (graph-theoretic aspects)
68W25: Approximation algorithms
Related Items
Simplex Partitioning via Exponential Clocks and the Multiway-Cut Problem, Consistency of Dirichlet Partitions, Effective Resistance Preserving Directed Graph Symmetrization, Unnamed Item, Unnamed Item, Local Flow Partitioning for Faster Edge Connectivity, Minimum Congestion Mapping in a Cloud, Comparison of Metric Spectral Gaps, The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative-Type Metrics into ℓ 1, Partitioning Well-Clustered Graphs: Spectral Clustering Works!, Continuum limit of total variation on point clouds, A derandomized approximation algorithm for the critical node detection problem, A randomized algorithm with local search for containment of pandemic disease spread, The complexity of finding uniform sparsest cuts in various graph classes, A class of semidefinite programs with rank-one solutions, A variational approach to the consistency of spectral clustering, On the complexity of isoperimetric problems on trees, Vertical perimeter versus horizontal perimeter, Variational perspective on local graph clustering, Quasimetric embeddings and their applications, Sparsest cut in planar graphs, maximum concurrent flows and their connections with the max-cut problem, Semidefinite and linear programming integrality gaps for scheduling identical machines, A tighter insertion-based approximation of the crossing number, Certifying global optimality of graph cuts via semidefinite relaxation: a performance guarantee for spectral clustering, Stagnation-aware breakout tabu search for the minimum conductance graph partitioning problem, A simple algorithm for the multiway cut problem, Partitioning a graph into small pieces with applications to path transversal, Approximating the rectilinear crossing number, Separator-based graph embedding into multidimensional grids with small edge-congestion, Terminal embeddings, Tighter spectral bounds for the cut size, based on Laplacian eigenvectors, Balanced tree partition problems with virtual nodes, \(d\)-dimensional arrangement revisited, Routing in Undirected Graphs with Constant Congestion, Approximating the Rectilinear Crossing Number, On the Hardest Problem Formulations for the 0/1 Lasserre Hierarchy, Combinatorial theorems about embedding trees on the real line, Integrality Gaps of Linear and Semi-Definite Programming Relaxations for Knapsack, Sparsest Cut in Planar Graphs, Maximum Concurrent Flows and Their Connections with the Max-Cut Problem, On the Hardest Problem Formulations for the $$0/1$$ Lasserre Hierarchy, Approximation Limits of Linear Programs (Beyond Hierarchies), Minimum Linear Arrangement of Series-Parallel Graphs
