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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.