An instance of Correlation Clustering is a complete graph \(G = (V, E)\) , where \(E = E^+\cup E^-\)  and \(E^+\cap E^- = \emptyset \) , and the goal is to compute a
partition \(\lbrace C_1,\ldots ,C_k\rbrace \)  of \(V\)  minimizing the number of the
\(+\) edges \((u,v)\)  where \(u \in C_i\)  and \(v \in C_j\) , \(i \ne j\) , plus
the number of the \(-\) edges \((u,v)\)  where \(u,v \in C_i\) . The following
standard LP relaxation has been used by most of the previous
work [1]}, [2]}, [3]}.
\(\min \sum _{ij \in E^+}x_{ij} &+ \sum _{ij \in E^-} (1-x_{ij})\\x_{ij} & \le x_{ik} + x_{jk} \quad \forall i,j,k \in V\\x_{ij} & \ge 0 \quad \forall i,j \in V.\) 
