How to partition a set in order to minimize the number of the elements and their interactions?
-
05-11-2019 - |
题
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?
没有正确的解决方案
不隶属于 cs.stackexchange