$O(\sqrt{\logn})$ Approximation to SPARSEST CUT in $\tilde{O}(n^2)$ Time
From MaRDI portal
Publication:3053148
DOI10.1137/080731049zbMath1207.68441OpenAlexW2103444054MaRDI QIDQ3053148
Satyen Kale, Sanjeev Arora, Elad Hazan
Publication date: 4 November 2010
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/080731049
graph partitioningmultiplicative weightssparsest cut problembalanced separator problemexpander flows
Related Items (15)
Organisational hierarchy constructions with easy Kuramoto synchronisation ⋮ Convergence and synchronization in networks of piecewise-smooth systems via distributed discontinuous coupling ⋮ Mean isoperimetry with control on outliers: exact and approximation algorithms ⋮ Combinatorial Fiedler theory and graph partition ⋮ An Escape Time Formulation for Subgraph Detection and Partitioning of Directed Graphs ⋮ UPGMA and the normalized equidistant minimum evolution problem ⋮ Euclidean distortion and the sparsest cut ⋮ The complexity of finding uniform sparsest cuts in various graph classes ⋮ \(d\)-dimensional arrangement revisited ⋮ On the advantage of overlapping clusters for minimizing conductance ⋮ The Complexity Status of Problems Related to Sparsest Cuts ⋮ The Normalized Graph Cut and Cheeger Constant: From Discrete to Continuous ⋮ Polynomial‐time algorithms for solving a class of critical node problems on trees and series‐parallel graphs ⋮ Connectivity Oracles for Graphs Subject to Vertex Failures ⋮ Randomized Approximation Schemes for Cuts and Flows in Capacitated Graphs
This page was built for publication: $O(\sqrt{\logn})$ Approximation to SPARSEST CUT in $\tilde{O}(n^2)$ Time
