Correlation Clustering with Sherali-Adams

Vincent Cohen-Addad, Euiwoong Lee, Alantha Newman

Given a complete graph $G=(V,E)$ where each edge is labeled $+$ or $-$, the Correlation Clustering problem asks to partition $V$ into clusters to minimize the number of $+$edges…