# Choose subsets to minimize a set function

Given two sets $$S_1$$ and $$S_2$$ of $$n$$ elements each and a capacity $$C$$. Each element in $$S_i$$ ($$i=1,2$$) has a weight $$w_{ij}$$ for $$j=1,2,\ldots,n$$. From each set $$S_i$$ ($$i=1,2$$), choose a subset $$O_i\subseteq S_i$$, where $$\sum_{j\in O_i}w_{ij}\leq C$$, in order to minimize the following function :

$$|O_2|-|O_1|+2|O_1\backslash O_2|-3|O_1\cup O_2|.$$

Can we solve this problem in polytime?

• I don't think so. Maximizing the number of items subject to knapsack constraints is not hard, isn't it? – zdm Feb 6 at 17:54
• It might be cleaner to state this as maximizing $2|O_1| + 2|O_2| - |O_1 \cap O_2|$. That's equivalent, and the function to minimize/maximize is less messy. – D.W. Feb 6 at 18:00
• How did you reformulate it? @D.W. – zdm Feb 6 at 18:05
• That's just an identity on sets: $$|O_2|-|O_1|+2|O_1\backslash O_2|-3|O_1\cup O_2| = - (2|O_1| + 2|O_2| - |O_1 \cap O_2|)$$ (this can be proven by writing down a Venn diagram, introducing three variables for $|O_1\setminus O_2|$, $|O_2\setminus O_1$, and $|O_1 \cap O_2|$, and expressing everything in terms of those three variables). Now minimizing $-\psi$ is always equivalent to maximizing $\psi$, for any expression $\psi$. – D.W. Feb 6 at 18:52
• @j_random_hacker when we choose the elements of $S_2$ as you suggested, my problem becomes equivalent to maximizing the number of items to put in the knapsack subject to the weights constraints, which i think is not hard. – zdm Feb 7 at 10:59