It has an integrality gap of 2 [1]}; consider a graph with
vertices \(\lbrace  0, 1, \dots , k \rbrace \)  where the edge \((0, i)\)  is \(+\)  for
each \(i \in [k]\)  and the rest are \(-\) . Letting \(x_{0i} = 1/2\)  for each
\(i \in [k]\)  and \(x_{ij} = 1\)  for each \(1 \le i < j \le k\)  ensures
that the LP value is \(k/2\) , but the optimal integral value is \(k - 1\) .
