-2
$\begingroup$

I have a problem that I need to prove its np-completness: My original question

I need to reduce it from some problem, i´m trying to do it from some other than knapsack, that´s why I ask again. I need two sets $A$ and $B$ of equal cardinality $|A|=|B|$ and $\sum{A}\leq V$ and $\sum{B}\leq V$.

  • It is like Partition, but sums must not be the same, must be less or equal than a fixed $V$, and cardinality must be equal.
  • It is also like Bin-Packing problem with $k = 2$ (numbers of bins), but need to guarantee equal cardinality.
  • I tried also with Sub-Set-Sum, but need to guarantee that the elements sum at most $k$, not exactly $k$.

Note: The problem with knapsack is that knapsack can select any items in no particular order from the list of objetcs, and my problem need to select (if selects) the first $k$ objects if they fit in the two sets.

PS: If anything is unclear, please comment and I'll explain!

$\endgroup$
  • 2
    $\begingroup$ This looks like it should be an edit to your previous question: this one can't be understood without reading that one. And why do you care whether or not the reduction is from knapsack? $\endgroup$ – David Richerby Jan 20 '17 at 16:45
  • $\begingroup$ Your problem looks similar to Select a subset of the columns in 2×n matrix, is it easy? $\endgroup$ – Zir Jan 20 '17 at 16:57
  • $\begingroup$ @DavidRicherby - It seems that it should, but I'm new to stackexchange site and didn't know whether I should have edited my previous question or create a new one. My mistake!. Also: I don't care if it is from Knapsack or not, it is just, i've tried from knapsack and I couldn't Do you have any idea? $\endgroup$ – DarK_FirefoX Jan 20 '17 at 18:50
  • $\begingroup$ @Zir - I read that article, and also had tried reduce it from EqualPartition but it needs the sum of the elements in the partition to be equal to a fixed $k$, and I need at most $k$. Any Idea how to get that? $\endgroup$ – DarK_FirefoX Jan 20 '17 at 18:52
1
$\begingroup$

Assuming that you have a set $S=\{b_1,\ldots,b_n\}$ and a number $V$ and you would like to find two subsets $X$ and $Y$ of $\{1,\ldots,n\}$ such that $\sum_{i\in X}b_i\leq V$ and $\sum_{i\in Y}b_i\leq V$ and $|X|=|Y|$.

Given an instance of EQUAL-PARTITION (EP) $E=\{a_1,\ldots,a_n\}$, are there two subsets $A$ and $B$ of $\{1,\ldots,n\}$ such that $\sum_{i\in A}a_i=\sum_{i\in B}a_i=\frac{\sum_{i=1}^na_i}{2}$ and $|A|=|B|$?

You construct an instance of your problem as follows:

$$b_i=a_i+\frac{2}{n}V-\frac{\sum_{i=1}^na_i}{n}.$$

Now, EP is solved iff your problem is solved.

  • For the only if case, assume that EP is solved, that is there are two subsets $A$ and $B$ of $\{1,\ldots,n\}$ such that $\sum_{i\in A}a_i=\sum_{i\in B}a_i=\frac{\sum_{i=1}^na_i}{2}$ and $|A|=|B|$. Take $X=A$ and $Y=B$. You will find that $\sum_{i\in X}b_i=V\leq V$ and $\sum_{i\in Y}b_i=V\leq V$ and $|X|=|Y|$.
  • For the if case, assume that you find two subsets $X$ and $Y$ of $\{1,\ldots,n\}$ such that $\sum_{i\in X}b_i\leq V$ and $\sum_{i\in Y}b_i\leq V$ and $|X|=|Y|$. Take $A=X$ and $B=Y$. You will find that $\sum_{i\in A}a_i\leq \frac{\sum_{i=1}^na_i}{2}$ and $\sum_{i\in B}a_i\leq \frac{\sum_{i=1}^na_i}{2}$ and $|A|=|B|$. Since $\sum_{i\in A}a_i+\sum_{i\in B}a_i=\sum_{i=1}^na_i$, you get $\sum_{i\in A}a_i=\sum_{i\in B}a_i=\frac{\sum_{i=1}^na_i}{2}$
$\endgroup$
  • $\begingroup$ Reading the answer and liking it! Trying to test it properly. But, one thing! What should I use as $V$ for my problem? $\endgroup$ – DarK_FirefoX Jan 20 '17 at 20:42
  • $\begingroup$ Take $V=\frac{\sum_{i=1}^{n}a_i}{2}$. $\endgroup$ – Zir Jan 20 '17 at 21:24
  • $\begingroup$ According to the construction you suggested for $b_i$ then if I take $V$ like that then $a_i$ will be equal to $b_i$. So I am left with the same! But your answer got me in a direction I'm working on, I will write the answer if get to something! $\endgroup$ – DarK_FirefoX Jan 20 '17 at 21:35
  • $\begingroup$ Well @Zir, Seing your answer give me an idea for the solution! The problem is I didn´t create the decision problem for my problem correctly. Aster giving thinking a bit more. My decision problem should have a value $k$ that stands for exactly how many items I should take. With that and EQUAL-PARTITION I had it. Thank you so much for your help! PS: I don´t know if I should Accept your answer or answer my self the question!? $\endgroup$ – DarK_FirefoX Jan 21 '17 at 13:07
  • $\begingroup$ I think you can answer the question if this answer doesn't satisfy you. $\endgroup$ – Zir Jan 21 '17 at 19: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.