Sublinear Algorithms for MAXCUT and Correlation Clustering

Aditya Bhaskara, Samira Daruki, Suresh Venkatasubramanian

We study sublinear algorithms for two fundamental graph problems, MAXCUT and correlation clustering. Our focus is on constructing core-sets as well as developing streaming algorith…