3
$\begingroup$

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)

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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!) $\endgroup$ – Neal Young Dec 14 '17 at 7:36
  • 2
    $\begingroup$ @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. $\endgroup$ – Abhishek Shetty Dec 14 '17 at 7:44
  • $\begingroup$ Oh you're right! My mistake! $\endgroup$ – Neal Young Dec 14 '17 at 8:02
  • $\begingroup$ 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$. $\endgroup$ – Jasper Lu Dec 14 '17 at 20:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.