# Select a subset of the columns in $3\times n$ matrix, is it NP-hard?

I want to know if this problem is NP-hard?

The problem: Given a non-negative integer-valued matrix of size $3\times n$ of the form

$$\begin{bmatrix} a_1 & \ldots & a_n\\ b_1 & \ldots & b_n\\ a_1b_1 & \ldots & a_nb_n\\ \end{bmatrix},$$

where $a_i,b_i$ are non-negative integers. Given four non-negative integer numbers $b<n$, $c_1$, $c_2$ and $c_3$.

The goal: Find a subset of the columns of cardinality at most $b$ such that (i) the sum of the first row over the subset of the columns is greater than $c_1$, (ii) the sum of the second row over the subset of the columns is greater than $c_2$ and (iii) the sum of the third row over the subset of the columns is less than $c_3$. Return no if no such subset exists. That is to say, is there exists a set $S$ of cardinality at most $b<n$ such that:

$$\sum_{i\in S}a_i\geq c_1,\\ \sum_{i\in S}b_i\geq c_2,\\ \sum_{i\in S}a_ib_i\leq c_3,$$

How to show that this problem is NP-hard?

Attempt:

Here is a "similar" NP-hard problem that I asked. This problem has as instance $(n,b,c,\mathbf{A})$ where $\mathbf{A}$ is given by $$\begin{bmatrix} x_1 & \ldots & x_n\\ y_1 & \ldots & y_n\\ \end{bmatrix},$$ I tried to reduce the previous problem to the new one as follows: choose $c_1=c_2=c$ and choose $c_3$ very big and create the matrix as follows:

$$\begin{bmatrix} x_1 & \ldots & x_n\\ y_1 & \ldots & y_n\\ x_1y_1 & \ldots & x_ny_n\\ \end{bmatrix},$$

Your problem is NP-complete, indeed. You can, e.g., reduce PARTITION to your problem. If you want to know if there is a subset of the set $\{d_1,\ldots,d_k\}$ that sums up to exactly $D := \frac{1}{2} \sum_{i=1}^k d_i$, you can use your problem by setting $b_i := 1$ and $a_i := d_i$ for all $i$ and by setting $c_1 := D$, $c_2 = 0$, and $c_3 := D$ as well as $b := n-1$.
• And $k$ in PARTITION is $n$ ? – Brika Feb 24 '16 at 20:03