Given n objects shared by several sets of known sizes, what is the minimum number of objects shared by all the sets?

58 Views Asked by At

Here is what seems to be an easy case. Suppose there are 13 objects and 3 sets A, B, and C of size 9 sharing those objects. Set A can have any 9 of the objects. Set B can have at most 4 objects not in A, so A and B share at least 5 objects. Set C must share at least 5 objects with A and 5 objects with B. C can only have 9 objects, so it must share at least one of them with both A and B. Is this reasoning correct?

How can the general case of such a problem be solved? You know the size of the union of all sets of objects and the sizes of each set. How can you determine the minimum size for the intersection of all the sets?

1

There are 1 best solutions below

4
On

A general approach is to use integer linear programming, with a nonnegative decision variable $x_S$ for each of the nonempty subsets $S$ of the given sets and linear constraints to enforce the cardinalities. For your example, the problem is to minimize $x_{111}$ subject to \begin{align} x_{001} + x_{011} + x_{101} + x_{111} &= 9 \\ x_{010} + x_{011} + x_{110} + x_{111} &= 9 \\ x_{100} + x_{101} + x_{110} + x_{111} &= 9 \\ x_{001} + x_{010} + x_{011} + x_{100} + x_{101} + x_{110} + x_{111} &= 13 \end{align} As you observed, the minimum objective value is $1$, attained by $x_{011}=x_{101}=x_{110}=4$, $x_{111}=1$, and all other $x_S = 0$.

The maximum objective value turns out to be $7$.