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?

(Cross-post from mathoverflow here: https://mathoverflow.net/questions/288136/np-hardness-of-finding-0-1-vector-to-maximize-rows-of-1-1-matrix)

This problem is NP-hard. In fact, even deciding whether there exists a choice of x such that all the dot products are positive is NP-complete. I show this below by reduction from set cover.

Reduction

Suppose we are given a set cover instance consisting of number $k$ and sets $S_1, S_2, \ldots, S_m \subseteq \{1,2,\ldots,n\}$. The corresponding question is whether there exists a subset $C$ of $\{1,2,\ldots,n\}$ with $|C| = k$ such that each $S_i$ contains at least one element of $C$ (or equivalently such that $S_i \cap C$ is non-empty for each $i$).

We use this input to construct an instance of your problem, that is, a set of vectors over $\{-1, 1\}$ of the same length. The length of these vectors is going to be $n+k+1$, and there will be $m+k+2$ of them. In particular, we will have vectors $a$, $b_1, b_2, \ldots, b_{k+1}$, and $c_1, c_2, \ldots, c_m$ as defined below.

Denote by $1(n)$ a vector of length $n$ whose values are all $1$s. Denote by $e_i(n)$ a vector of length $n$ whose $i$th value is $1$ and whose other values are $-1$. Denote by $s_j$ a vector of length $n$ whose $i$th value is $1$ if $i \in S_j$ and $-1$ otherwise.

Then

• $a = [~1(k+1)~;~-1(n)~]$
• $b_j = [~e_j(k+1)~;~1(n)~]$ for $1 \le j \le k+1$ and
• $c_j = [~-e_1(k+1)~;~s_j~]$ for $1 \le j \le n$

Correctness

Let $x = [~x'~;~x''~]$ be any vector of $0$s and $1$s expressed as two subvectors $x'$ and $x''$ of lengths $k+1$ and $n$.

Suppose that the dot product of $x$ with vectors $a$, $b_1$, $\ldots$, and $b_{k+1}$ is positive. Then consider the two vectors $a$ and $b_j$ (for some $j$). These two vectors are almost exactly negatives of each other. In particular, they both have $1$ as the $j$th component but are otherwise negatives of each other (this is easy to verify). Then if $x$ is a vector of $0$s and $1$s with a $0$ in the $j$th component, the dot product of $x$ with $a$ is the negative of the dot product of $x$ with $b_j$. In this case, these two dot products cannot both be positive. Therefore, $x$ must have a $1$ in the $j$th component.

The above logic can be applied for every $j$ with ($1 \le j \le k+1$). From this, we can conclude that if $x$ has a positive dot product with vectors $a$, $b_1$, $\ldots$, and $b_{k+1}$, then $x' = 1(k+1)$.

Furthermore, we know that $x \cdot a > 0$, and $$x \cdot a = [~x'~;~x''~] \cdot [~1(k+1)~;~-1(n)~]= [~1(k+1)~;~x''~] \cdot [~1(k+1)~;~-1(n)~] = 1(k+1) \cdot 1(k+1) + x'' \cdot -1(n) = k+1 - |x''|_1$$ where $|x''|_1$ is the number of $1$s in $x''$, so $k+1-|x''|_1 > 0$ and $|x''|_1 < k+1$.

Similarly, $x \cdot b_1 > 0$, and $$x \cdot b_1 = [~x'~;~x''~] \cdot [~e_1(k+1)~;~1(n)~]= [~1(k+1)~;~x''~] \cdot [~e_1(k+1)~;~1(n)~] = 1(k+1) \cdot e_1(k+1) + x'' \cdot 1(n) = -(k-1) + |x''|_1,$$ so $-(k-1)+|x''|_1 > 0$ and $|x''|_1 > k-1$.

Together the above implies that $|x''|_1 = k$. To summarize, we have shown that if $x$ has a positive dot product with vectors $a$, $b_1$, $\ldots$, and $b_{k+1}$, then $x' = 1(k+1)$ and $|x''|_1 = k$. In fact, it is easy to verify that the reverse is also true. In other words, $x = [~x'~;~x''~]$ has a positive dot product with vectors $a$, $b_1$, $\ldots$, and $b_{k+1}$ if and only if $x' = 1(k+1)$ and $|x''|_1 = k$.

From now on, consider only vectors $x$ of the above form. Notice that there is a one to one correspondence between possible vectors $x''$ and subsets of $\{1, \ldots, n\}$ of size $k$: in particular, $x''$ can be put into correspondence with set $X \subseteq \{1, \ldots, n\}$ with $|X| = k$ such that $(x'')_i = 1$ iff $i \in X$.

Under this correspondence, we can consider the necessary and sufficient conditions for $x$ to have positive dot product with vectors $c_1$, $\ldots$, and, $c_n$.

For any $j$, we can expand $x \cdot c_j$ as $$x \cdot c_j = [~1(k+1)~;~x''~] \cdot [~-e_1(k+1)~;~s_j~] = 1(k+1) \cdot -e_1(k+1) + x'' \cdot s_j = (k-1) + x'' \cdot s_j.$$ Notice that the value of $x'' \cdot s_j$ is exactly a sum of $k$ components of $s_j$: in particular, $x'' \cdot s_j = \sum_{i \in X}(s_j)_i$. If these $k$ components are all $-1$s, then this sum is $-k$, and so $x \cdot c_j = (k-1) + x'' \cdot s_j = (k-1) + -k = -1 < 0$. If these $k$ components include at least one $1$, then this sum is at least $-1\times(k-1) + 1\times 1 = -(k-2)$ in which case $x \cdot c_j = (k-1) + x'' \cdot s_j \ge (k-1) + -(k-2) = 1 > 0$. Thus, we see that $x \cdot c_j \ge 0$ for a specific $j$ if and only if $X$ includes at least one $i$ such that $(s_j)_i = 1$.

Remember that $(s_j)_i = 1$ if and only if $i \in S_j$. Thus, $x \cdot c_j \ge 0$ for a specific $j$ if and only if $X$ includes at least one $i$ such that $i \in S_j$, or equivalently if and only if $X \cap S_j$ is non-empty.

Then $x \cdot c_j \ge 0$ for every $j$ if and only if for every $j$, $X \cap S_j$ is not empty. Notice that the latter condition is exactly equivalent to the condition that $X$ is a solution to the input set cover instance.

In summary, we see that $x$ is a vector of $0$s and $1$s with positive dot product with all the vectors produced by the reduction if and only if $x = [~1(k+1)~;~x''~]$ with $|x''|_1 = k$ and $x''$ corresponds to a set $X \subseteq \{1, \ldots, n\}$ with $|X| = k$ such that $X$ is a solution to the input instance of set cover. In other words, a solution to the set cover instance exists if and only if a solution to the instance produced by the reduction exists.

• Hi, Mikhail. Could you please provide a source we can cite for this reduction? Commented Jul 31 at 9:17
• Hi. Unfortunately, I don't have a source to cite as this was an original proof that I came up with to answer this question. Feel free to cite this answer or this page in general if you need a citation. Commented Aug 2 at 2:48

There is a simple algorithm that achieves $1/2$ approximation.

Pick the column with highest number of $1$s, let it be $C_j$. Let $s$ denote the number of $1$s in $C_j$. Pick $x$ to be $1_{\{j\}}$ i.e. all zeros except at index $j$. We can get $s$ vectors among the given vectors with positive dot product with $x$.

Now, we claim that $s$ is at least $\text{OPT}/2$, where $\text{OPT}$ is the optimal answer. Pick an optimal solution $x^*$. Consider the submatrix induced by the rows which have positive sum. In this submatrix, pick a smaller submatrix with the columns $j$ such that $x^*_j =1$. In the final submatrix, sum of each row is positive, and thus overall sum is positive. This implies that there exists some column with positive sum. That column has at least $\text{OPT}/2$ $1$s, which proves the required claim.

• Your argument cannot be correct. Consider the case when $M$ is the $n\times n$ identity matrix. OPT is $n$, but your algorithm chooses just one index $j$, so gives a solution of value 1. I think the flaw in your argument is that, in your submatrix, the column with positive sum does not have to have OPT/2 1's in the submatrix. It just has to have more ones than minus ones. (But it can have many zeros!) Commented Dec 14, 2017 at 7:36
• @NealYoung I don't think the matrix is allowed to have the value $0$. The matrix is $\{-1,1\}$ valued but the vectors being evaluated are $\{0,1\}$ valued. Commented Dec 14, 2017 at 7:44
• Oh you're right! My mistake! Commented Dec 14, 2017 at 8:02
• There's actually a simpler proof of that. Suppose $s$ is not at least $OPT/2$, and that $s$ has $k \ +1$s in it. Then, let $OPT=2k+1$. $s$ must have $k+1\ -1$s in it. If $s$ is not at least $OPT/2$ then we must be able to combine a bunch of columns with $k\ +1$s in it to make $2k+1$ rows positive. However, since there are also $k+1\ -1$s, whenever we choose a column to include, we are "dropping" more rows than we are picking up, so to say. So, $s$ must be $OPT/2$. Commented Dec 14, 2017 at 20:55