# Find the minimal subset of rows of some matrix such that the sum of each column over this rows exceeds some threshold

Let $$A$$ be a an $$n\times m$$ real valued matrix. The problem is to find the minimal subset $$I$$ of rows (if there is any) such that the sum of each column $$j$$ over the corresponding rows exceeds some threshold $$t_j$$, i.e. $$\sum_{i\in I}A[i,j]>t_j$$ for all $$j\in\{1,\dots m\}$$.

Or, stated as optimization problem:

Let $$A\in\mathbb{R}^{n\times m}, t\in\mathbb{R}^m$$. Now solve \begin{align}\min_{\xi\in\{0,1\}^n}&\sum_{i=1}^n\xi_i\\\text{s.t.}&\,A^\top\xi>t\,.\end{align}

Actually, i would need a solution only for $$m=2$$, but the general might be interesting too.

The general $$n \times m$$ case is easily seen to be NP-hard by reduction from set cover. Add a column for each element; each row is the indicator function of a subset; set $$t_j = 0$$ for each column.
A slightly more complicated reduction from subset sum shows that this is NP-hard even for $$m = 2$$. Suppose we are given a subset sum problem instance where we have a set $$B$$ of integers and the goal is to find a subset of $$B$$ that sums to exactly $$k$$. We reduce this to your problem as follows: for each integer $$b \in B$$, add $$[b, -b]$$ as a row to $$A$$; then set $$t_1 = k - 1$$ and $$t_2 = -k - 1$$. This enforces that the sum of the chosen subset must be greater than or equal to $$k$$ and also less than or equal to $$k$$, and therefore exactly equal to $$k$$.