A lot of effort has focused on understanding the approximability of
the original version introduced by [1]}: the unweighted case
on a complete graph. (For the rest of the paper, Correlation Clustering denotes this
version.) In this case, [1]} gave a PTAS for the maximization
version and an \(O(1)\) -approximation for the minimization version.
Charikar, Guruswami, and Wirth gave a 4-approximation based on
rounding the standard linear programming (LP) relaxation and proved
APX-hardness [3]}. Ailon, Charikar, and Newman gave a
combinatorial 3-approximation algorithm based on choosing random
pivots and a 2.5-approximation by combining this pivot based approach
with the standard LP relaxation [4]}.
