3
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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$.

For solving this problem in practice, I would recommend an integer linear programming solver. Most such solvers have direct support for 0-1 variables, so the linear optimization version you describe in the question can be presented to the solver exactly as written.

| cite | improve this answer | |
$\endgroup$

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.