1

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 ...


Only top voted, non community-wiki answers of a minimum length are eligible