2
$\begingroup$

I am trying to solve the following problem:

Given a binary matrix $\mathbf{A} \in \{0,1\}^{m \times n}$ and a vector $\mathbf{b} \in \mathbb N^n$, does there exist a binary vector $\mathbf{c} \in \{0,1\}^n$ which satisfies the following requirements?

  1. $\mathbf{c}^\top \mathbf{b} < x$, where $x$ is a given threshold.

  2. $\mathbf{c}^\top$ is a linear combination of the rows in matrix $\mathbf{A}$.

My attempts so far have been concentrated on constructing all possible binary vectors with the dimension $1\times n$, checking requirement number 1 for all these vectors, and then checking requirement number 2 for all the vectors that satisfied requirement number 1. This brute force approach has been hopelessly ineffective as n and m can get quite large.

How can I solve this problem in a more efficient way than my brute force approach?

The problem illustrated with a fictional example:

Say that employees within a firm are free to request aggregated income data for groups of departments within said firm. Requests will only be granted if the requested groups do not identify the aggregated income of a group with less than $x$ people. To check whether each requested group by itself satisfies this requirement is trivial. However, multiple groups can be requested and so there must also be checks in place to find out whether the groups in combination can allow for the identification of the income of groups with less than $x$ people.

In this example the matrix and vectors can be interpreted as follows:

Matrix A: Each row represents a requested group and each column represents a department. The value '1' signifies that the department is included in the group, '0' that it is not.

Vector b: includes information on how many employees there are in each department.

Thus, the existence of a binary vector that satisfies the two requirements will imply that the request for data should be declined.

I decided to include this example in case my interpretation of the problem is flawed or just needlessly restrictive. All help is greatly appreciated.

Edit:

As an example I choose to set $x = 4$ and define $A$ and $b$ as follows:

$$A = \begin{pmatrix}1 & 1 & 1 \\\ 0 & 1 & 0 \\\ 0 & 0 & 1\end{pmatrix}\ \ \ \ \ \ \ \ \ b = \begin{pmatrix}2 \\\ 5 \\\ 7 \end{pmatrix} $$

As explained above, matrix $A$ represents requested groups (rows) of departments (columns). Vector $b$ contains information on how many employees there are in each department. In this example it is clear that all of the requested groups by themselves will satisfy the condition that they are not identifying the aggregated income of a group with less than four people. We can check this by calculating:

$$Ab = \begin{pmatrix} 14 \\\ 5 \\\ 7\end{pmatrix}$$

We see that there are five or more employees in all of the groups. However, if we in matrix $A$ subtract row two and three from row one, we see that we can identify the aggregated income of the department in column one of matrix $A$. This department only has two employees, and thus a linear combination of the requested groups allows for the identification of the aggregated income of a group with only two people! This means that a request for these groups of departments should be declined. This example yields $c^T$ as the following binary vector, which satisfies both of the conditions:

$$c^T=\begin{pmatrix} 1 & 0 & 0\end{pmatrix}$$

If we drop the third row from matrix $A$ a binary vector $c^T$ which satisfies both conditions will not exist.

$\endgroup$
  • $\begingroup$ Shouldn't you require $cb>x$? $\endgroup$ – Richard Sep 22 at 16:15
  • 1
    $\begingroup$ Since you're not trying to optimise on $c$, you can solve the problem trivially by making $c$ a combination of all rows. If that passes the check you're good. If it doesn't, then no request can. $\endgroup$ – Richard Sep 22 at 16:18
  • $\begingroup$ Richard, you are correct that for the request to be granted that $cb \geqslant x$ needs to hold. I took the opposite approach of trying to check whether the request should be declined. Thank you for your suggestion. I will try it out and see if I can get it to work. $\endgroup$ – afallafa Sep 23 at 12:53
  • $\begingroup$ If $\mathbf{c}^\top$ is a linear combination of the rows in matrix $\mathbf{A}$, then it is a very special linear combination indeed, for both $\bf A$ and $\bf c$ are binary. $\endgroup$ – Rodrigo de Azevedo Sep 23 at 13:39
  • 1
    $\begingroup$ @MPIchael I have now added an example in the question where $c^T$ does exist, and one where it does not exist. $\endgroup$ – afallafa Sep 26 at 13:50
0
$\begingroup$

First, calculate row-sums of the matrix A. That should be n times m operations. Store the row-sums into a vector-like structure with their row index. Sort this vector by size with quisort or the like: (operations: n*m + O(n LOG(N))). Then start from the lowest row sum and check whether the condition holds for this row alone. Work your way up the sorted array.

The idea is, that since b only has positive numbers, those rows with more ones in them will be closer to violating the criterion. You start with that row, with is most likely to pass the second criterion. That at least answers the question of existance of one such vectors. It may not give a speedup for finding all of them, although linear cominations of those rows which have been sorted low are more likely to pass..

Do you have any more information on A and b, other than the one stated? The problem may have very different charracteristics depending on that. (If you have a million matrix rows which are zero, sorting them will be a waste, etc.)

EDIT:

Designing an algorithm for this, my approach would be to somehow sort the work in a way, so that the most likely candidates (rows/row-combinations) are checked first. The way I described only helps with finding a row which satisfies the conditions on its own. Maybe you can flip the problem around. If we look at the vector, the easiest (most likely) way to find a linear combination, is to find combinations for the rows with low values in b. If your vector is: $b=(1,1,3,8,999)$, then i would start brute forcing by looking for combinations which will isolate the first entries.

$\endgroup$
  • $\begingroup$ I like this solution in terms of checking whether any of the rows in matrix $A$ satisfies both conditions, but I don't see how it accounts for linear combinations of the rows. $\endgroup$ – afallafa Sep 26 at 13:56
  • $\begingroup$ If you want to efficiently answer the question: "Does there exist...?", then I'd still check the easy/fast stuff first!:-) $\endgroup$ – MPIchael Sep 26 at 14:13
  • $\begingroup$ I guess I probably won’t be able to find a silver bullet which drastically simplifies the problem. In that case this is probably my best approach. Thanks! $\endgroup$ – afallafa Sep 27 at 6:56

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.