3
$\begingroup$

Let $B$ and $C$ be collections of finite sets. We say that $B$ is a normal basis of $C$ if for all $c\in C$ there is a pairwise disjoint subcollection of $B$ whose union is exactly $c$.

The input of the normal set basis problem is a collection $C$ of finite sets and an integer $k\geq 1$, and we need to decide whether $C$ has a normal basis whose size is at most $k$.

The normal set basis problem is known to be NP-complete. Is it known whether the problem has a polynomial 2-approximation deterministic algorithm, or whether it is hard to approximate?

$\endgroup$

0

Your Answer

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