Before we present the full algorithm, we briefly discuss some intuition behind our rounding.
In [1]} and [2]}, the analysis boiled
down to analyzing the ratio defined in (REF ) on each type of triangle.
We call a triangle \(+++\)  if it has three \(+\) edges, and \(++-\) , \(+--\) ,
\(---\)  triangles are defined similarly. For the LP rounding
algorithm of [1]}, each triangle has a ratio of at most 2,
except the \(++-\)  triangle, which has a ratio of \(2.5\) . In
[2]}, there is a trade-off by lowering the ratio for the
\(++-\)  triangles but increasing the ratio for the \(+++\)  triangles, to
the point where each ratio is around \(2.06\) .
