Efficiently finding binary vectors satisfying multiple conditions

Question

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.

Answer 1

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.