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?



Your Answer

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