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>



NP-hardness of finding 0-1 vector to maximize rows of {-1, +1} matrix
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. 


