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

2021/10/02 by Nimita Shinde, Shinde, Nimita, Vishnu Narayanan +3
Business, Management and Accounting · Computer Science · #Advanced Clustering Algorithms Research #Advanced Graph Neural Networks #Complexity and Algorithms in Graphs #Data Management and Algorithms #FOS: Mathematics #Facility Location and Emergency Management #Optimization and Control (math.OC)

paper · pdf · doi:10.48550/arxiv.2110.00779

openalex publication_date 2021/10/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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²) 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

Citations

• A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization
• Sketchy Decisions: Convex Low-Rank Matrix Optimization with Optimal Storage

Related

• Sublinear Algorithms for MAXCUT and Correlation Clustering
• Understanding the Cluster LP for Correlation Clustering
• Correlation Clustering with Vertex Splitting
• Correlation Clustering in Data Streams
• Correlation Clustering in Constant Many Parallel Rounds