Packing sets to maximize overlap For a set of sets $A$, let $\cup A := \cup_{S \in A} S$.

Consider the following problem:

Input: 


a list of $m$ weights $w = (w_1, \ldots, w_m)$,
a list of $n$ distinct subsets $T = (S_1, \ldots, S_n)$ such that $\bigcup_{S\in T} S = [m]$,
an integer $k$.


Let $P$ be a partition of $T$. 
We say $P$ is a $k$-good partition when
the size of each part is at most $k$:
$\forall p \in P \ |p| \leq k$.
The cost of $P$ is defined as 
the sum of weight of items counted once for each part they appear in, i.e.
$$cost(P) := \sum_{p\in P} \ \sum_{x\in \cup p} w_x $$

Output: a $k$-good partition of $P$ of $T$ minimizing $cost(P)$.


  What is the complexity of this problem?
  Is it NP-hard or is there a polynomial-time algorithm?




Example:
$m = 7$, $w=(2,2,3,4,1,2,2)$,
$n = 3$, $T=(S_1=\{1,2,3\}, S_2=\{3,4,5\}, S_3=\{5,6,7\})$
$k=2$

In this case, since $k&lt;|T|$, 
it is obvious that more than one partition is 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 optimal $P$ is $\{S_1, S_2\}, \{S_3\}$ with the total cost 12+5=17.



The unweighted version (when the weights of the elements are all 1) 
is also very interesting to me.
I believe it's NP-hard, by a reduction from min-balanced cut.  Given a graph $G=(V,E)$ and integer $\ell$, min-balanced cut asks whether there is a cut that is balanced (has $|V|/2$ vertices on each side), and cuts at most $\ell$ edges.  Given $G$ and $\ell$, construct the following instance of your problem.  For each vertex $v$, create a set $S_v$ containing the edges incident to $v$.  Take $k=|V|/2$.  Then the (minimal) $k$-good partitions are partitions of the sets into two equal-size groups, corresponding to the balanced cuts of $G$, and your (unweighted) cost for such a solution equals $|E|$ plus the number of edges cut.  Unless I'm mistaken :-).

EDIT: Similarly you can reduce the following problem to yours: given a graph $G=(V,E)$ and integer $\ell$, color the vertices of $G$ so that each color class has at most $k$ vertices, minimizing the number of edges whose two endpoints have the same color.  (The reduction: make a set $S_v$ for each vertex $v\in V$, containing the pairs $\{v,w\}$ not in $E$.)