Expander flows, geometric embeddings and graph partitioning

DOI10.1145/1007352.1007355zbMath1192.68467OpenAlexW2020632401MaRDI QIDQ5901073

Sanjeev Arora, Umesh V. Vazirani, Satish B. Rao

Publication date: 15 August 2010

Published in: Proceedings of the thirty-sixth annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1007352.1007355

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (47)

Improved approximating \(2\)-CatSP for \(\sigma\geq 0.50\) with an unbalanced rounding matrix ⋮ Crossing number, pair-crossing number, and expansion ⋮ A note on multiflows and treewidth ⋮ Approximation algorithms for the weighted \(t\)-uniform sparsest cut and some other graph partitioning problems ⋮ Metric extension operators, vertex sparsifiers and Lipschitz extendability ⋮ An improved approximation ratio for the minimum linear arrangement problem ⋮ Coarse differentiation and multi-flows in planar graphs ⋮ \(\ell ^2_2\) spreading metrics for vertex ordering problems ⋮ Approximation algorithms for requirement cut on graphs ⋮ Asymptotic negative type properties of finite ultrametric spaces ⋮ A derandomized approximation algorithm for the critical node detection problem ⋮ A randomized algorithm with local search for containment of pandemic disease spread ⋮ Spectral partitioning works: planar graphs and finite element meshes ⋮ Unbalanced graph partitioning ⋮ General variable neighborhood search for computing graph separators ⋮ Fast balanced partitioning is hard even on grids and trees ⋮ The bi-objective critical node detection problem ⋮ Clustering and outlier detection using isoperimetric number of trees ⋮ Compression bounds for Lipschitz maps from the Heisenberg group to \(L_{1}\) ⋮ Unnamed Item ⋮ Approximation algorithms via contraction decomposition ⋮ Expander graphs and their applications ⋮ Towards strong nonapproximability results in the Lovász-Schrijver hierarchy ⋮ Euclidean distortion and the sparsest cut ⋮ Moment inequalities for sums of random matrices and their applications in optimization ⋮ Graph clustering ⋮ Improved Approximation Guarantees through Higher Levels of SDP Hierarchies ⋮ On the advantage of overlapping clusters for minimizing conductance ⋮ A semidefinite programming approach to the hypergraph minimum bisection problem ⋮ Analysis of set-up time models: a metric perspective ⋮ Advances in metric embedding theory ⋮ Cut problems in graphs with a budget constraint ⋮ The Complexity Status of Problems Related to Sparsest Cuts ⋮ On average distortion of embedding metrics into the line ⋮ Fréchet embeddings of negative type metrics ⋮ On graph parameters guaranteeing fast sandpile diffusion ⋮ Linear time algorithms for approximating the facility terminal cover problem ⋮ Approximation algorithms for the Bipartite Multicut problem ⋮ Inoculation strategies for victims of viruses and the sum-of-squares partition problem ⋮ Algorithmic Extensions of Cheeger’s Inequality to Higher Eigenvalues and Partitions ⋮ Random Walks, Electric Networks and The Transience Class problem of Sandpiles ⋮ On Khot’s unique games conjecture ⋮ An \(O(\sqrt n)\)-approximation algorithm for directed sparsest cut ⋮ Quasisymmetric embeddings, the observable diameter, and expansion properties of graphs ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Balanced partitions of trees and applications

This page was built for publication: Expander flows, geometric embeddings and graph partitioning