0
$\begingroup$

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}, $$

$\endgroup$
4
$\begingroup$

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

$\endgroup$
  • $\begingroup$ And $k$ in PARTITION is $n$ ? $\endgroup$ – Brika Feb 24 '16 at 20:03

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.