A simpler and parallelizable
O
( √ log
n
)-approximation algorithm for Sparsest Cut
Vladimir Kolmogorov
.
Accepted to
ACM Transactions on Algorithms
(
TALG
), 2025. Preliminary version appeared in
ACM Symposium on Parallelism in Algorithms and Architectures
(
SPAA
), June 2024.
Links
arXiv