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

<h2>Reduction</h2>

<p>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$).</p>

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

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

<p>Then</p>

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

<h2>Correctness</h2>

<p>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$. </p>

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

<p>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)$.</p>

<p>Furthermore, we know that $x \cdot a &gt; 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 &gt; 0$ and $|x''|_1 &lt; k+1$.</p>

<p>Similarly, $x \cdot b_1 &gt; 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 &gt; 0$ and $|x''|_1 &gt; k-1$.</p>

<p>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$. </p>

<p>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$.</p>

<p>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$.</p>

<p>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 &lt; 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 &gt; 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$. </p>

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

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

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

CC BY-SA 4.0
2024-07-31T09:17:45.093Z
Hi, Mikhail. Could you please provide a source we can cite for this reduction?
leplata
CC BY-SA 4.0
2024-08-02T02:48:30.290Z
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.
Mikhail Rudoy
CC BY-SA 3.0
2017-12-17T21:31:23.040Z
2017-12-17T21:31:23.040Z
Mikhail Rudoy
<p>There is a simple algorithm that achieves $1/2$ approximation. </p>

<p>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$. </p>

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

CC BY-SA 3.0
2017-12-14T07:36:04.977Z
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!)
Neal Young
CC BY-SA 3.0
2017-12-14T07:44:33.153Z
@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.
Abhishek Shetty
CC BY-SA 3.0
2017-12-14T08:02:13.693Z
Oh you're right!  My mistake!
Neal Young
CC BY-SA 3.0
2017-12-14T20:55:56.203Z
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$.
Jasper Lu
CC BY-SA 3.0
2017-12-13T09:21:08.747Z
2017-12-14T08:05:19.287Z
2017-12-14T08:05:19.287Z
saisandeep
<p>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$.</p>

<p>For example, for the collection of vectors given by the rows of the matrix
$$ \begin{bmatrix} -1 &amp; -1 &amp; -1 &amp; -1 \\ +1 &amp; +1 &amp; -1 &amp; -1 \\ +1 &amp; -1 &amp; +1 &amp; -1 \\ -1 &amp; +1 &amp; +1 &amp; -1 \\ -1 &amp; -1 &amp; -1 &amp; -1 \end{bmatrix} $$
the optimal choice of $x$ is $[1,\ 1,\ 1,\ 0]^T$, which has positive dot products with the middle three rows.</p>

<p>Is this problem known to be NP-hard? If so, are any polynomial-time approximation algorithms available?</p>

<p>(Cross-post from mathoverflow here: <a href="https://mathoverflow.net/questions/288136/np-hardness-of-finding-0-1-vector-to-maximize-rows-of-1-1-matrix">https://mathoverflow.net/questions/288136/np-hardness-of-finding-0-1-vector-to-maximize-rows-of-1-1-matrix</a>)</p>

<cc.complexity-theory><co.combinatorics><optimization><np>
NP-hardness of finding 0-1 vector to maximize rows of {-1, +1} matrix
Jasper Lu
# NP-hardness of finding 0-1 vector to maximize rows of {-1, +1} matrix

(Asked by: username_0 on 2017-12-11)

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

**Tags:** cc.complexity-theory, co.combinatorics, optimization, np

---

## 2 answers

### Answer by username_1 on 2017-12-17. Score: 4

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.

> **Comments:**
> **username_2**: Hi, Mikhail. Could you please provide a source we can cite for this reduction?  
> **username_1**: 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.  

---

### Answer by username_3 on 2017-12-13. Score: 2

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.

> **Comments:**
> **username_4**: 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!)  
> **username_5**: @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.  
> **username_4**: Oh you're right!  My mistake!  
> **username_0**: 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$.  

---

