# Tag Info

Consider the natural LP relaxation of this problem, i.e., $-1 \leq x_{i} \leq 1$ for every $x_i \in \{x_1,\dotsc,x_n\}$. Then, using the relaxation techniques, no approximation algorithm is possible since the integrality gap for this LP is $\infty$. Proof: Consider any instance of this problem that has a non-zero cost. Then, in the relaxed LP, you make \$x_i ...