Correlation Clustering Beyond the Pivot Algorithm

We study the classic correlation clustering problem. Given n objects and a complete labeling of the object-pairs as either "similar" or "dissimilar", the goal is to partition the objects into arbitrarily many clusters while minimizing disagreements with the labels.