Problem Detail: I want to know if this problem is polynomial-time solvable or not? The problem is: Given a nonnegative integer-valued matrix of size $2times 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.
Asked By : Brika
Answered By : Yuval Filmus
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}. $$
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/52657 Ask a Question Download Related Notes/Documents
