Expander flows, geometric embeddings and graph partitioning
From MaRDI portal
Publication:5899507
DOI10.1145/1502793.1502794zbMath1325.68255OpenAlexW2088844265WikidataQ56503925 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
Semidefinite programming (90C22) Deterministic network models in operations research (90B10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)
Related Items
Flow-Based Algorithms for Improving Clusters: A Unifying Framework, Software, and Performance ⋮ Quantum Speedup for Graph Sparsification, Cut Approximation, and Laplacian Solving ⋮ On the Hardest Problem Formulations for the $$0/1$$ Lasserre Hierarchy ⋮ Approximation Limits of Linear Programs (Beyond Hierarchies) ⋮ From graph cuts to isoperimetric inequalities: convergence rates of Cheeger cuts on data clouds ⋮ Minimum Linear Arrangement of Series-Parallel Graphs ⋮ Optimization over the Boolean hypercube via sums of nonnegative circuit polynomials ⋮ Large data limit for a phase transition model with the p-Laplacian on point clouds ⋮ Vertical perimeter versus horizontal perimeter ⋮ Sparsest Cut in Planar Graphs, Maximum Concurrent Flows and Their Connections with the Max-Cut Problem ⋮ Unnamed Item ⋮ A derandomized approximation algorithm for the critical node detection problem ⋮ A randomized algorithm with local search for containment of pandemic disease spread ⋮ 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 ⋮ Simplex Partitioning via Exponential Clocks and the Multiway-Cut Problem ⋮ Mean isoperimetry with control on outliers: exact and approximation algorithms ⋮ Tighter spectral bounds for the cut size, based on Laplacian eigenvectors ⋮ Certifying global optimality of graph cuts via semidefinite relaxation: a performance guarantee for spectral clustering ⋮ Iterated multilevel simulated annealing for large-scale graph conductance minimization ⋮ Consistency of Dirichlet Partitions ⋮ Sum of Squares Bounds for the Empty Integral Hull Problem ⋮ Balanced tree partition problems with virtual nodes ⋮ An Escape Time Formulation for Subgraph Detection and Partitioning of Directed Graphs ⋮ Approximating the Rectilinear Crossing Number ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Interactions of computational complexity theory and mathematics ⋮ On the Hardest Problem Formulations for the 0/1 Lasserre Hierarchy ⋮ The complexity of finding uniform sparsest cuts in various graph classes ⋮ Effective Resistance Preserving Directed Graph Symmetrization ⋮ \(d\)-dimensional arrangement revisited ⋮ Dynamic Balanced Graph Partitioning ⋮ Multi-way sparsest cut problem on trees with a control on the number of parts and outliers ⋮ Bounds on maximum concurrent flow in random bipartite graphs ⋮ Semi-random Graphs with Planted Sparse Vertex Cuts: Algorithms for Exact and Approximate Recovery ⋮ The Small Set Vertex expansion problem ⋮ Variational perspective on local graph clustering ⋮ Combinatorial theorems about embedding trees on the real line ⋮ On the Structure of Isometrically Embeddable Metric Spaces ⋮ Mildly Exponential Time Approximation Algorithms for Vertex Cover, Balanced Separator and Uniform Sparsest Cut ⋮ Comparison of Metric Spectral Gaps ⋮ Integrality Gaps of Linear and Semi-Definite Programming Relaxations for Knapsack ⋮ Partitioning Well-Clustered Graphs: Spectral Clustering Works! ⋮ A class of semidefinite programs with rank-one solutions ⋮ A tighter insertion-based approximation of the crossing number ⋮ Stagnation-aware breakout tabu search for the minimum conductance graph partitioning problem ⋮ Local Flow Partitioning for Faster Edge Connectivity ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ A variational approach to the consistency of spectral 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 simple algorithm for the multiway cut problem ⋮ Unnamed Item ⋮ Convex programming based spectral clustering ⋮ Routing in Undirected Graphs with Constant Congestion ⋮ Connectivity Oracles for Graphs Subject to Vertex Failures ⋮ Communities, Random Walks, and Social Sybil Defense ⋮ On the complexity of isoperimetric problems on trees ⋮ Partitioning a graph into small pieces with applications to path transversal ⋮ Simplex Transformations and the Multiway Cut Problem ⋮ A (1+epsilon)-Approximation for Makespan Scheduling with Precedence Constraints Using LP Hierarchies ⋮ The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative-Type Metrics into ℓ 1 ⋮ Approximating the rectilinear crossing number ⋮ Separator-based graph embedding into multidimensional grids with small edge-congestion ⋮ Minimum Congestion Mapping in a Cloud ⋮ Time optimal consensus tracking with multiple leaders ⋮ Metric-Constrained Optimization for Graph Clustering Algorithms ⋮ Continuum limit of total variation on point clouds
