Our high-level setup of the analysis also follows from that
of [1]} and [2]}. Consider the \(t\) -th iteration of
Algorithm REF  with the current graph \(G_t = (V_t, E_t)\) . Let
\(\mathsf {cost}^r_p(u, v)\)  be the probability that \((u, v)\)  is violated in the
rounding algorithm when \(p\)  is the pivot, and \(\mathsf {lp}^r_p(u, v)\)  be the LP
value of \((u, v)\)  (i.e., \(x_{uv}\)  if \((u, v)\)  is \(+\)  and \(y_{uv}\)  if
it is \(-\) ) times the probability that \((u, v)\)  disappears (i.e.,
\(\Pr [S \cap \lbrace  u, v \rbrace  \ne \emptyset ]\) ). The superscript \(r\)  stands for rounding.
