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?

没有正确的解决方案

许可以下: CC-BY-SA归因
不隶属于 cs.stackexchange
scroll top