2
$\begingroup$

Given two sets $S_1$ and $S_2$ of $n$ elements each. Each set $S_1$ (resp. $S_2$) has a revenue $R_1$ (resp. $R_2$). Each element $i$ of $S_1$ (resp. $S_2$) has a gain $g_{i1}$ (resp. $g_{i2}$). From set $S_1$ (resp. $S_2$), choose a subset of elements $O_1$ (and $O_2$) such that:

  • $\sum_{i\in O_1}g_{i1}\geqslant R_1$;
  • $\sum_{i\in O_2}g_{i2}\geqslant R_2$;
  • $|O_1|+|O_2|+|O_1\cap O_2|$ is minimized.

Can we solve this problem in polynomial-time?

I started by a greedy approach which chooses the elements by increasing order of their gains. I tried few examples but this does not provide optimal results.

I am now trying to prove that it is NP-hard using a reduction from PARTITION. Any hints?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

Consider the following two variants of subset sum problem:

Variant 1

Given a set of $2n$ positive integer elements and a positive integer target $W$, is there a subset with size $n$, whose sum is $W$?

Variant 2

Given a set of $n$ positive integer elements and a positive integer target $W$, where $(\text{the maximum element})< 2\times(\text{the minimum element})$, is there a subset whose sum is $W$?

Variant 1 is NP-hard by a reduction from one-in-three 3-SAT (almost the same reduction from 3SAT to the normal subset sum problem, except that we do not need the $s$ and $t$ values, and the target is always $111\ldots1$).

Variant 2 is also NP-hard by a reduction from Variant 1. Given an instance of Variant 1, we add a large enough integer $M$ to each element so that the new elements satisfy the constraint in Variant 2. Now the answer to Variant 1 is "yes" if and only if there is a subset of the new elements whose sum is $W+nM$ (since $M$ is large enough, the subset must have size $n$).

Now we show a reduction from Variant 2 to (the decision version of) your problem, so your problem is NP-hard.

Given an instance of Variant 2, we construct $S_1=S_2$ as the same set as the given instance. Let $s$ denote the sum of all elements. We set $R_1=W$ and $R_2=s-W$. The gain of each element is the same as itself.

Now if there is a subset $O\subseteq S_1=S_2$ whose sum is $W$, then we can choose $O_1=O$ and $O_2=S_2\backslash O$, meaning there is a solution to your problem with $|O_1|+|O_2|+|O_1\cap O_2|\le n$.

On the other hand, if there is a solution to your problem with $|O_1|+|O_2|+|O_1\cap O_2|\le n$, then $2|O_1\cap O_2|\le n-|O_1\cup O_2|$. Let $\min$ and $\max$ be the minimum and maximum elements respectively. We have $$\sum_{e\in O_1\cap O_2}e\le |O_1\cap O_2|\max\le 2|O_1\cap O_2|\min\le(n-|O_1\cup O_2|)\min\le\sum_{e\notin O_1\cup O_2}e.$$

This means $$ \sum_{e\notin O_1}e=\sum_{e\in O_2}e-\sum_{e\in O_1\cap O_2}e+\sum_{e\notin O_1\cup O_2}e\ge \sum_{e\in O_2}e\ge s-W. $$

Note $\sum_{e\in O_1}e\ge W$ and $\sum_{e\notin O_1}e+\sum_{e\in O_1}e=s$, we have $\sum_{e\in O_1}e=W$ and $\sum_{e\notin O_1}e =s-W$, which means there is a subset $O\subseteq S_1=S_2$ whose sum is $W$.

Improve this answer
$\endgroup$
8
  • $\begingroup$ Thanks. Is the variant 2 known in the literature? Do you mean that the gains are constructed so that the max gain is at most twice the min gain? $\endgroup$
    – zdm
    Commented Mar 15, 2019 at 15:30
  • $\begingroup$ @zdm The max gain is at most twice the min gain because so is the input of Variant 2, not because of the construction. I don't think Variant 2 is studied in the literature because it is trivial. $\endgroup$
    – xskxzr
    Commented Mar 15, 2019 at 15:35
  • $\begingroup$ In the reduction from Variant 1 to Variant 2, say I have an instance of Variant 1 as follows: $\{1,2,3,4,5,6\}$ and $W=11$. How can I choose $M$ ? $\endgroup$
    – zdm
    Commented Mar 15, 2019 at 16:25
  • $\begingroup$ @zdm It is enough to let $M$ be the sum of all elements. In your example we can choose $M=21$. $\endgroup$
    – xskxzr
    Commented Mar 15, 2019 at 16:32
  • $\begingroup$ I tried some examples with your reduction. Given an instance of Variant 2, when I create an instance of my problem I always find a solution with $O_1\cap O_2=\emptyset$. Does this mean that the problem is still NP-hard even if I want to minimize $|O_1|+|O_2|$? $\endgroup$
    – zdm
    Commented Mar 15, 2019 at 22:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.