Min-Max Correlation Clustering via Neighborhood Similarity

Nairen Cao, Steven Roche, Hsin-Hao Su

We present an efficient algorithm for the min-max correlation clustering problem. The input is a complete graph where edges are labeled as either positive $(+)$ or negative $(-)$,…