A simpler and parallelizable O( n)-approximation algorithm for \textsc{Sparsest Cut}
From MaRDI portal
Publication:6907340
Cites work
- \(O(\sqrt{\log n})\) approximation to sparsest cut in \(\tilde{O}(n^2)\) time
- A combinatorial, primal-dual approach to semidefinite programs
- A data structure for dynamic trees
- An efficient parallel solver for SDD linear systems
- Approximating fractional multicommodity flow independent of the number of commodities
- Breaking the multicommodity flow barrier for o(√log n)-approximations to sparsest cut
- Distributed sparse cut approximation
- Dynamic spanning forest with worst-case update time: adaptive, Las Vegas, and \(O(n^{1/2-\epsilon})\)-time
- Expander flows, geometric embeddings and graph partitioning
- Fast algorithms for directed graph partitioning using flows and reweighted eigenvalues
- Graph partitioning using single commodity flows
- scientific article; zbMATH DE number 5485558 (Why is no real title available?)
- scientific article; zbMATH DE number 1256718 (Why is no real title available?)
- Improved distributed expander decomposition and nearly optimal triangle enumeration
- Maximum flow and minimum-cost flow in almost-linear time
- Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
- Non-interactive correlation distillation, inhomogeneous Markov chains, and the reverse Bonami-Beckner inequality
- On distance scales, embeddings, and efficient relaxations of the cut cone
- Parallel approximate maximum flows in near-linear work and polylogarithmic depth
- Positivity improving operators and hypercontractivity
- Towards an SDP-based approach to spectral methods: a nearly-linear-time algorithm for graph partitioning and decomposition
This page was built for publication: A simpler and parallelizable \(O(\sqrt{\log n})\)-approximation algorithm for \textsc{Sparsest Cut}
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6907340)
