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

Nimita Shinde, Vishnu Narayanan, James Saunderson

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 M…