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

arXiv: https://arxiv.org/abs/2110.00779 · HTML: https://mlsanity.com/paper/2110.00779/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Oct 2021.

## Built on by (most cited first, 2 of 2)

- [Riemannian Optimization on Relaxed Indicator Matrix Manifold](https://mlsanity.com/paper/2503.20505/) (2025)
- [Suboptimality bounds for trace-bounded SDPs enable a faster and scalable low-rank SDP solver SDPLR+](https://mlsanity.com/paper/2406.10407/) (2024)

## Abstract (arXiv)

Max-k-Cut and correlation clustering are fundamental graph partitioning problems. For a graph with 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) variables and constraints. 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.