Options
Memory-Efficient Approximation Algorithms for MAX-K-CUT and Correlation Clustering
Journal
Advances in Neural Information Processing Systems
ISSN
10495258
Date Issued
2021-01-01
Author(s)
Shinde, Nimita
Narayanan, Vishnu
Saunderson, James
Abstract
MAX-K-CUT and correlation clustering are fundamental graph partitioning problems. For a graph G = (V, E) with n vertices, the methods with the best approximation guarantees for MAX-K-CUT and the MAX-AGREE variant of correlation clustering involve solving SDPs with O(n2) constraints and variables. Large-scale instances of SDPs, thus, present a memory bottleneck. In this paper, we develop simple polynomial-time Gaussian sampling-based algorithms for these two problems that use O(n + |E|) memory and nearly achieve the best existing approximation guarantees. For dense graphs arriving in a stream, we eliminate the dependence on |E| in the storage complexity at the cost of a slightly worse approximation ratio by combining our approach with sparsification.
Volume
10