
To improve beyond the integrality gap of the standard LP, we
naturally use the Sherali-Adams hierarchy tailored for Correlation Clustering,
defined in Section REF . Previous algorithms [1]}, [2]} proceed by sampling a random pivot \(p \in V\)  in each
iteration and independently deciding whether \(v \in V \setminus \lbrace  p\rbrace \)  belongs to \(p\) 's cluster or not. In order to use the power of
Sherali-Adams, we adapt the correlated rounding that has been
used for Constraint Satisfaction Problems
(CSPs) [3]}, [4]}, [5]}. One of the main advantages is that
for \(u, v \in V \setminus \lbrace  p \rbrace \) , one can ensure that \(\Pr [u\mbox{and }v\mbox{ belong to }p\mbox{'s cluster}]\)  is approximately
equal to the value predicted by the Sherali-Adams solution in an
amortized sense. See Section  for the description of
the algorithm.

Previous analyses [1]}, [2]} employ the elegant triangle-based analysis that bounds the ratio
\(\frac{\mathsf {cost}_u(v, w) + \mathsf {cost}_v(w, u) + \mathsf {cost}_w(u, v)}{\mathsf {lp}_u(v, w) + \mathsf {lp}_v(w, u) + \mathsf {lp}_w(u, v)},\) 
for each triangle \((u, v, w)\) , where \(\mathsf {cost}_u(v, w)\)  is the
probability that \((v, w)\)  is violated when \(u\)  is pivot, and \(\mathsf {lp}_u(v,w)\)  is the probability that \(v\)  or \(w\)  belongs to \(u\) 's cluster
(removing \((v, w)\)  from the instance) times the LP contribution of
\((v, w)\) . (See Section REF  for this basic setup.) The
previous analyses bound the above ratio for every triangle
individually. With our rounding algorithm, the
ratio (REF ) is already at most 2 for every triangle,
and there is only one type of a bad triangle that has a ratio
close to 2 (i.e., \(++-\)  triangles with LP values close to \(0.5, 0.5,1\)  respectively, which are bad triangles for the previous rounding
algorithms as well). We prove that the number of such bad triangles is
not large compared to chargeable triangles that have
significantly smaller ratios but still with large denominators. This
allows a global charging scheme where we show that the total ratio
(the sum of numerators over all triangles / the sum of denominators
over all triangles) is strictly less than
2. Sections REF  and REF  show how we
use this scheme to finish the analysis.

