Pergunta

The Minimum Cardinality Exact Cover (MCEC) problem is just like set cover, but the output sets must be disjoint.

Formally, given a collection of subsets $S$ of a finite set $U$, the problem asks for a subcollection $S'$ of $S$ of minimum cardinality such that the union of $S'$ is $U$, and $S_1 \cap S_2 = \emptyset$ for every distinct $S_1, S_2 \in S'$.

We may assume that for each $u \in U$' there is a set $S_u = \{u\}$ in $S$. This ensures that there exists an exact cover of cardinality at most $|U|$.

I'd like to know if MCEC is as hard to approximate as set cover, i.e. cannot be approximated to within a $\log |U|$ factor. I can show that MCEC has no constant factor approximation, reducing from $k$-Set-Cover for any constant $k$ by adding every subset of a set present in the set cover input. But having the same inapproximability as set cover would be stronger.

Nenhuma solução correta

Licenciado em: CC-BY-SA com atribuição
Não afiliado a cs.stackexchange
scroll top