I am working on a problem that arises in the design of experiments. I wonder if it is part of a well-studied class of problems.

The problem is:

Start with a set of points $S$ and a target partition of that set $P$.

Let $\mathcal{P}$ be a set of partitions of $S$ not including $P$

The problem is to “cover” $P$ using the minimal number of partitions from $\mathcal{P}$

To make this more formal, a subset of the set of partitions $\tilde{\mathcal{P}}\subset \mathcal{P}$ covers $P$ if the meet of $\tilde{\mathcal{P}}$ (the coarsest partition finer than all partitions in $\tilde{\mathcal{P}}$) is finer than $P$.


For example, suppose the target partition is $P=\big\{\{1,2\},\{3\},\{4\},\{5,6\}\big\}$ and $\mathcal{P}=\Big\{\big\{\{1\},\{2,3,4,5,6\}\big\};\big\{\{1,2,3\},\{4,5,6\}\big\};\big\{\{1,2\},\{3,4\}\{5,6\}\big\}\Big\}$

We only need two partitions from $\mathcal{P}$ to cover this. The meet of $\Big\{\big\{\{1,2,3\},\{4,5,6\}\big\};\big\{\{1,2\},\{3,4\}\{5,6\}\big\}\Big\}$ is $P$ and this is the minimal way to cover $P$ from $\mathcal{P}$.

What I’ve tried:

I have tried to map my problem into a set covering problem with no luck. I got hung up with the meet operation operating differently than the union in set covering.



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.