A Note on the Inapproximability of Correlation Clustering

Jinsong Tan

We consider inapproximability of the correlation clustering problem defined as follows: Given a graph $G=(V,E)$ where each edge is labeled either "+" (similar) or "-" (dissimilar…