Here's the problem:I have a collection of collections, $C$, where each $c\in C$ is a collection of sets $X\subset U$.  Denote $c_i$ as the i-th $X$ in $c$.  Informally, I want to map all the sets in each collection to bins, where no two sets in a single collection can occupy the same bin, such that the sum of the sizes of the unions of all sets in each bin is minimized.  More formally:Let $N = \max_{c \in C} |c|$, and let $P_N$ be the set of all permutations of all non-empty subsets of the set $\{1,2,...,N\}$.  I wish to define a mapping:$$F : C \rightarrow P_{N},\ s.t.\ \forall c \in C\ (|F(c)| = |c|)$$with bin sets$$B(k) = \{X \subset U : \exists c \in C\ (\exists i \in \{1,2,...,|c|\}\ s.t.\ c_i = X \wedge (F(c))_i = k)\}$$Such that the quantity$$\sum_{k=1}^{N} { \Biggl|\bigcup_{X \in B(k)}\Biggr| } $$is minimized.Off the bat, I'd guess that this is an NP-hard problem - a reduction from Set Cover seems to be just within reach.  Even a greedy algorithm that iteratively processes each collection $c \in C$, producing minimal results each time, requires $O(2^N \cdot |C|)$ time using dynamic programming, where $|U|$ is assumed to be a constant factor.I'm having trouble proving whether or not the Greedy algorithm is even optimal - or if a more efficient solution exists.  Anyone have any thoughts?Alternatively, minimizing the quantity:$$\max_{1 \leq k \leq N} {\Biggl| \bigcup_{X \in B(k)} \Biggr| }$$Is also of interest.  It's definitely a different problem, as demonstrated by a simple case where $C$ has 2 collections, one of the form $\{\{1\}, \{3, 4\}\}$, and the other $\{\{2\}, \{3, 4\}\}$.  I am not sure this problem is any easier though
Overlap Maximization problem
algorithms;time complexity;optimization;sets