# 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

• one approach: for two vectors $v_i$ and $v_j$, we say $v_i\geq v_j$ iff the summation of the entries of $v_i$ (weight of $v_i$) is greater or equal to the summation of the entries of $v_j$. Without loss of generality, we arrange the vectors $v_i$ in a matrix with their descending weight (so $v_1$ has maximum weight). Now, we say two vectors $v_i$ and $v_j$ are pined in $k$ place if these two vectors have $k$ common positive entries in same position. In next step, we must find vectors with positive weight which has the greatest pined number two by two. I will write some more later... – Shahrooz Janbaz Dec 11 '17 at 9:55
• @JasperLu : You might try asking this question at cstheory.stackexchange.com – Timothy Chow Dec 11 '17 at 16:27
• @TimothyChow done. Thanks for the heads up – Jasper Lu Dec 11 '17 at 20:20
• FYI, simultaneously cross-posting on two or more Stack Exchange sites is not permitted. @TimothyChow, can I make a request for the future? In the future, when recommending another site, perhaps you could let them know not to cross-post? (You can suggest that they delete the copy here before posting elsewhere, if they think it's a better fit elsewhere.) This might provide a better experience for all. Thanks for listening! – D.W. Dec 12 '17 at 2:37
• @TimothyChow, notice that I mentioned simultaneous cross-posting. The default policy for Stack Exchange is "no cross-posting at all" (see here). Sites can override that if they choose. CSTheory has chosen to adopt a more permissive policy that disallows simultaneous cross-posting but allows cross-posting if certain criteria are met (must wait at least a week, must cross-link, the other site must permit it too, please update both questions based on responses on the other site). – D.W. Dec 12 '17 at 2:57

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.

• Hi, thanks for the response. I am not sure if I understand your first paragraph properly. Could you give an example? From what I understand, you are splitting a variable x into x1 and x2 such that you are forcing both of them to be selected together. But I am a little lost in the construction. Also, given a 7/8 approximation bound for MAX-3SAT, do you think your reduction is approximation-preserving? If so, we might have a free inapproximability bound. – Jasper Lu Dec 13 '17 at 6:22
• @JasperLu Create a chat thread and I'll gladly discuss any unclear details with you. Whether it is approximation-preserving or not, I'm not sure yet because you can lose just a little bit on the forcing Hadamard part and then pairs $(0,1)$ and $(1,0)$ are no longer excluded, which screws up the rest quite thoroughly. If we can enhance the forcing part so that even satisfying $7/8$ of it would kill mixed pairs, then the rest will go through nicely but I do not see how to do it yet. – fedja Dec 13 '17 at 23:00
• Since I do not have enough reputation, I had a friend create a room here: chat.stackexchange.com/rooms/70198/… – Jasper Lu Dec 14 '17 at 2:57
• @JasperLu Excellent! Let's continue there :) – fedja Dec 14 '17 at 4:15

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.

• Your suggestion applies to any problem in NP. But the term "approximation algorithm" usually refers to an algorithm that is guaranteed to get within a certain factor of the optimum. LP relaxations don't always have this property. – Timothy Chow Dec 11 '17 at 16:13
• @TimothyChow: I agree but it's still better than nothing. Also, the simplicity of the given ILP may suggest connection to other known computational problems. – Max Alekseyev Dec 12 '17 at 14:06