2
$\begingroup$

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$.

Example

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.

$\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.