Memory-Efficient Approximation Algorithms for Max-k-Cut and Correlation Clustering.

Max-k-Cut and correlation clustering are fundamental graph G=(V,E) partitioning problems. The methods with the best approximation guarantees for Max-k-Cut and the Max-Agree variant of correlation clustering involve solving SDPs with $n^2$ variables and $n^2$ constraints (where $n$ is the number of vertices). Large-scale instances of SDPs, thus, present a memory bottleneck. In this paper, we develop a 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.