NP-hardness of finding 0-1 vector to maximize rows of {-1, +1} matrix Consider the following discrete optimization problem: given a collection of $m$-dimensional vectors $\{ v_1, \dots, v_n \}$ with entries in $\{-1, +1\}$, find an $m$-dimensional vector $x$ with entries in $\{0,1\}$ that maximizes the number of vectors $v_i$ having positive dot product with $x$.
For example, for the collection of vectors given by the rows of the matrix
$$ \begin{bmatrix} -1 & -1 & -1 & -1 \\ +1 & +1 & -1 & -1 \\ +1 & -1 & +1 & -1 \\ -1 & +1 & +1 & -1 \\ -1 & -1 & -1 & -1 \end{bmatrix} $$
the optimal choice of $x$ is $[1,\ 1,\ 1,\ 0]^T$, which has positive dot products with the middle three rows.
Is this problem known to be NP-hard? If so, are any polynomial-time approximation algorithms available?
EDIT: Cross-posted to cstheory stackexchange here: https://cstheory.stackexchange.com/questions/39735/np-hardness-of-finding-0-1-vector-to-maximize-rows-of-1-1-matrix
 A: Here is a simple embedding of 3-SAT into the current setup (the question is just if we can get all vectors good).
Call the first column special with $1$'s. 
Split the other variables into pairs $(a,b)\in\{(0,0),(1,1),(1,0),(0,1)\}$. 
Our first task will be to eliminate any $(1,0)$ or $(0,1)$ options. For that,
use the Hadamard matrix without the identically $1$ column, interpreting $1$ as $(-1,1)$ and $-1$ as $(1,-1)$ and put $1$ in the special column in these rows. Then the sum of dot products without special column is $0$ and if we have a single pair of bad type, some dot product is not $0$, so we have $\le -1$ somewhere forfeiting our chance. Also we forfeit it if we use $0$ for the special variable. Using $1$ for the special variable and having only $(0,0)$ and $(1,1)$ in the pairs is still OK.
So, put $-1$ in the remaining rows in the special column.
Now we have 3 options for other "pair entries" in the matrix: $(-1,-1),(1,-1),(1,1)$, which effectively work as $-2,0,2$ against $(0,0)$ and $(1,1)$ interpreted as $0$ and $1$ respectively, so we'll switch to this new representation.
Use the first 3 (new) variables as controls. We will use only $0$ and $2$ for them in the matrix, so, obviously, the controls should be all set to $1$.
Also, since everything is even now, we can forget about the cutoff at $+1$
(forced by the special column) and come back to the $0$ cutoff with the matrix entries $-1,0,1$.
Now if we have Boolean $a,b,c$ 
and a 3-disjunction with them, we will create the corresponding row where we put $0$ everywhere except the corresponding variables and controls. The remaining 6 entries are as follows:
$a\vee b\vee c$ - $0,0,0$ controls, $1$ at $a,b,c$;
$\bar a\vee b\vee c$ - $1,0,0$ controls, $-1$ at $a$, $1$ at $b,c$;
$\bar a\vee \bar b\vee c$ - $1,1,0$ controls, $-1$ at $a,b$, $1$ at $c$.
$\bar a\vee \bar b\vee \bar c$ - $1,1,1$ controls, $-1$ at $a,b,c$.
So the exact solution is, indeed, NP. As to approximations up to a constant factor, I don't know yet. 
A: The problem can be posed as the following (0,1)-integer programming problem:
$$\begin{cases}
y_1+\dots+y_n \longrightarrow \min\\
y_i \in \{0,1\}, &  i=1,\dots,n, \\
x_j \in \{0,1\}, &  j=1,\dots,m,\\
v_{i,1} x_1 + \dots + v_{i,m} x_m + (m+1)y_i \geq 1,& i=1,\dots,n.
\end{cases}$$
Correspondingly, it can be approximately solved in polynomial time via LP relaxation.
