On the hardness of constraint satisfaction

Question

I am interested in the hardness of the following question.

Suppose we have a vector of $n$ optimization variables $\mathbf{x} = \langle x_1, . . ., x_n\rangle $ and $m$ vectors $\mathbf{v}_1, . . .,\mathbf{v}_m$ with each $\mathbf{v}_j \in \{-1,1\}$.

Our objective is to maximize the number of nonnegative dot products between $\mathbf{x}$ and each $\mathbf{v}_j$, where each $0\leq x_i\leq 1$.

That is

$$\max_{\mathbf{x}}\sum_{j=1}^n\mathbb{I}[\langle \mathbf{x}, \mathbf{v}_j\rangle \geq 0]$$

$$\text{such that} 0\leq x_i \leq 1$$

These constitute linear constraints and I know in general that maximizing the number of satisfied linear constraints is NP, but these constraints differ in two main ways. The first is that none have a bias term, and the second is that each coefficient of the optimization variables is either 1 or -1.

Answer 1

As pointed out by Antti Röyskö the solution $\mathbf{x} = 0$ always maximizes the objective function since $\sum_{j=1}^n\mathbb{I}[\langle \mathbf{x}, \mathbf{v}_j\rangle \geq 0]$ corresponds to the number of constraints $\langle \mathbf{x}, \mathbf{v}_j\rangle \geq 0$ which are satsificed, and $\mathbf{x}$ satifies all constraints.

However, the problem becomes much more interesting if we dont allow degenerate solutions. In fact, by removing $\mathbf{x} = 0$, the problem goes from having a closed form solution, to being NP-hard. It takes a bit of work, but you can actually reduce any integer feasibility program down to your problem.