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

Max-k-Cut and correlation clustering are fundamental graph partitioning\nproblems. For a graph with G=(V,E) with n vertices, the methods with the best\napproximation guarantees for Max-k-Cut and the Max-Agree variant of correlation\nclustering involve solving SDPs with $O(n^2)$ variables and constraints.\nLarge-scale instances of SDPs, thus, present a memory bottleneck. In this\npaper, we develop simple polynomial-time Gaussian sampling-based algorithms for\nthese two problems that use $O(n+|E|)$ memory and nearly achieve the best\nexisting approximation guarantees. For dense graphs arriving in a stream, we\neliminate the dependence on $|E|$ in the storage complexity at the cost of a\nslightly worse approximation ratio by combining our approach with\nsparsification.\n