7
$\begingroup$

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

$\endgroup$

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.