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