Sublinear Time and Space Algorithms for Correlation Clustering via Sparse-Dense Decompositions

Sepehr Assadi, Chen Wang

We present a new approach for solving (minimum disagreement) correlation clustering that results in sublinear algorithms with highly efficient time and space complexity for this pr…