7
$\begingroup$

I want to know if this problem is polynomial-time solvable or not?

The problem is: Given a nonnegative integer-valued matrix of size $2\times n$ and two nonnegative integer numbers $b<n$ and $c$.

The question is: Find a subset of the columns of cardinality at most $b$ such that the sum of each row over the subset of the columns is greater than $c$. Return no if no such subset exists.

I cannot show it is NP-hard.

EDIT:

My attempt to prove hardness: According to the suggestions by Filmus, I tried to reduce PARTITION (an instance is given by the set of non-negative integers $\{a_1,\ldots,a_n\}$) to my problem. I failed of course. The think that I did not understand is how partitioning a set of non-negative integers is related to this problem? I mean in my problem I want to choose a subset of $\{1,\ldots,n\}$ in order to maximize something. I cannot see how this is a partition. I tried many thinks but I cannot write them all here:

  • I tried to create the matrix with only $a_{2i}$ in the first row and $a_{2i+1}$ in the second row.
  • I tired to make the first row sorted in increasing order and the second row sorted in the decreasing order.
  • I tried to divide the $a_i$ into two values $\alpha_i$ and $\beta_i$ such that $a_i=\alpha_i+\beta_i$ and then create the matrix with $\alpha_i$ in the first row and $\beta_i$ in the second row.

Can someone explain to me, intuitively, how can I use PARTITION to show the NP-hardness of my problem? You do not have to give the solution.

My solution to solving the problem:

I tried this solution. Suppose, without lose of generality that the first row of the matrix is sorted in increasing order. (The second row of the matrix does not have to be sorted otherwise the problem is trivial.)

Now, take the last $b$ columns of the matrix.

  • If the sum over the first row is less than $c$ than we are done. No solution exists.
  • Else, the sum of the first row over the last $b$ columns is greater than $c$, then see the sum of the second row.
    • If the sum of the second row over the last $b$ columns is greater than $c$ than we are done. Return the last $b$ columns.
    • Else, the sum of the first row over the $b$ columns is greater than $c$ but the sum of the second row over the $b$ columns is less than $c$. Well, here we have a problem.
$\endgroup$
  • $\begingroup$ At this point it is difficult to give a hint without giving away the solution. $\endgroup$ – Yuval Filmus Feb 11 '16 at 10:41
  • $\begingroup$ I added the solution to my answer. Next time try harder before giving up. $\endgroup$ – Yuval Filmus Feb 11 '16 at 13:28
6
+50
$\begingroup$

Hint: Show that it is NP-hard by reduction from EQUAL-PARTITION, the variant of PARTITION in which we require both parts to have equal sizes (see a question on math.se).

Given an instance $\{x_1,\ldots,x_n\}$ of EQUAL-PARTITION (with $x_i > 0$), consider an instance of your problem with $b = n/2$, $c = \sum_i (M+x_i)/2 - 1$ for large enough $M$ (I think that $M = \max_i x_i$ should suffice), and the matrix $$ \begin{bmatrix} M+x_1 & \cdots & M+x_n \\ M+\frac{\sum_i x_i}{n/2}-x_1 & \cdots & M+\frac{\sum_i x_i}{n/2}-x_n \end{bmatrix}. $$

$\endgroup$
  • $\begingroup$ Thank you. I tried to do it using PARTITION as you suggested. Given an instance of PARTITION, $A=\{a_1,\ldots,a_n\}$. I create an instance of my problem as follows: $b=n/2$ (I suppose that $n$ is even), $c=\sum_{i=1}^na_i/2$ and the matrix is given by $\begin{bmatrix}a_1 & \ldots & a_n\\ a_1 & \ldots & a_n\end{bmatrix}$. PARTITION is solved iff the problem is solved where the subset of columns are the ones with indices in the first partition or second partition. I think this is not exactly correct, right? $\endgroup$ – Brika Feb 4 '16 at 17:07
  • $\begingroup$ Your instance is easy to solve – take the $n/2$ largest non-negative $a_i$s, and see if they sum up to at least $\sum_i a_i/2$. So no, it doesn't work. Try to write a formal proof next time. Also, make sure to check out the exact definition of PARTITION (for example on Wikipedia). $\endgroup$ – Yuval Filmus Feb 4 '16 at 18:55
  • 5
    $\begingroup$ @Yuval. The matrix has non-negative entries, isn't it? $\endgroup$ – zighalo Feb 11 '16 at 13:40
  • 4
    $\begingroup$ Ah - I missed that condition. But perhaps the reduction can be adjusted somehow. $\endgroup$ – Yuval Filmus Feb 11 '16 at 14:02
  • 2
    $\begingroup$ @Brika Not necessarily. The idea works if suitably modified. $\endgroup$ – Yuval Filmus Feb 11 '16 at 22: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.