#StackBounty: A subset grouping problem

Bounty: 50

I’m trying to reduce the following problem to a more well-known formulation.

I have a bunch of subsets ${S_i }_{i in I}$ of some finite set.

I would like to put them into (disjoint) groups ${ G_j }{j in J}$ such that $max{j in J} left| bigcup {S in G_j} right|$ is as small as possible.
The number of groups $|J|$ is a fixed constant $k$.

An example: $k = 2$, $S_1 = {a, b}$, $S_2 = {b, c}$.

If $G_1 = {S_1}$ and $G_2 = {S_2}$, then

$$ max_{j in J} left| bigcup {S in G_j} right| = max{|S_1|, |S_2|} = 2$$

If instead $G_1 = {S_1, S_2}$ and $G_2 = {}$, then

$$ max_{j in J} left| bigcup {S in G_j} right| = max{|S_1 cup S_2|, |{}|} = 3$$

so the latter grouping is worse than the former.


Get this bounty!!!

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.