Packing sets to maximize overlap
We are given a set of $m$ elements ${e_1,...,e_m}$ that form our universe $\mathcal{U}$. Each element of our universe is further associated with a positive weight $w(e_j)$ with $j\in {1,...m}$. We are further given a collection $S={S_1,...S_n}$ of subsets of $\mathcal{U}$ whose union equals the universe. The intersection of any two sets in $S$ may be non-empty (i.e. subsets may overlap with each other).
Furthermore,
1) we are given an infinite number of configurations; each configuration can host up to $k$ subsets from $S$. There is no cost for using a configuration.
2) When assigning 2 or more subsets to one configuration and there is an overlap between the sets (i.e. 690
an element is part of more than one set) we pay the weight of that element only once. Obviously, there can be no overlap between subsets when considering different configurations.
Objective:
we want to assign each subset of $S$ to exactly one configuration in such a way that the weighted sum of the elements over all configurations is minimized. Consider the following example:
$\mathcal{U}={a,b,c,d,e,f,g}$,
$w(a)=2$
$w(b)=2$
$w(c)=3$
$w(d)=4$
$w(e)=1$
$w(f)=2$
$w(g)=2$
$S={S_1, S_2, S_3},$
$S_1={a,b,c}, S_2={c,d,e}, S_2={e,f,g}$
$k=2$
In this case, since $k<|S|$, it is obvious that more than one configurations are needed. Moreover, $S_1$ and $S_2$ should be packed together in the same configuration because of their heavy overlap ($S_1 \cap S_2$ gives the biggest overlap in our example - we pay 3 less cost units). So, the total cost of such an assignment is 12+5=17 and 2 configurations are needed.
Any ideas on how to prove that the problem is indeed intractable? Any ideas on how to calculate a good bound on the number of configurations that are needed?
The unweighted version (when the weights of the elements are all 1) is also very interesting to me. However, I did not manage to find something so far in the literature also for this problem.
Thank you! 690