16
$\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?

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

$\endgroup$
  • $\begingroup$ 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... $\endgroup$ – Shahrooz Janbaz Dec 11 '17 at 9:55
  • 2
    $\begingroup$ @JasperLu : You might try asking this question at cstheory.stackexchange.com $\endgroup$ – Timothy Chow Dec 11 '17 at 16:27
  • $\begingroup$ @TimothyChow done. Thanks for the heads up $\endgroup$ – Jasper Lu Dec 11 '17 at 20:20
  • 1
    $\begingroup$ 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! $\endgroup$ – D.W. Dec 12 '17 at 2:37
  • 2
    $\begingroup$ @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). $\endgroup$ – D.W. Dec 12 '17 at 2:57
8
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Jasper Lu Dec 13 '17 at 6:22
  • $\begingroup$ @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. $\endgroup$ – fedja Dec 13 '17 at 23:00
  • $\begingroup$ Since I do not have enough reputation, I had a friend create a room here: chat.stackexchange.com/rooms/70198/… $\endgroup$ – Jasper Lu Dec 14 '17 at 2:57
  • $\begingroup$ @JasperLu Excellent! Let's continue there :) $\endgroup$ – fedja Dec 14 '17 at 4:15
0
$\begingroup$

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.

$\endgroup$
  • 6
    $\begingroup$ 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. $\endgroup$ – Timothy Chow Dec 11 '17 at 16:13
  • 1
    $\begingroup$ @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. $\endgroup$ – Max Alekseyev Dec 12 '17 at 14:06

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.