Let $U = [1..n]$ be the universe of $n$ elements and $C$ be a collection of subsets of $U$, $C= S_1, \dots, S_m$, where $S_i \subset U$. Then the problem is to find as many partitions of $C$, such that each partition covers the universe U. The hardness results can be derived for this problem, but are there any approximation algorithms known for this ? I gather that the geometric version of this problem has some approximation algorithms, but is there any thing known in the general case ?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
Yes, this is closely related to the Domatic Partition problem. See the paper below. http://epubs.siam.org/doi/abs/10.1137/S0097539700380754
One can get the following results. Given a set cover instance let $k$ be the minimum over all elements in $U$, the number of sets that contain that element. Then it is clear that we can have at most $k$ disjoint set covers. The paper above shows that there always exist $\max\{1, k/(c \log n)\}$ disjoint set covers where $c$ is a sufficiently large constant. This immediately gives an $O(\log n)$-approximation. Moreover, it is hard to approximate to within this factor (modulo constants). And there are examples where the number of disjoint set covers is $O(k/\log n)$.
-
$\begingroup$ You mean mapping the collection C to a hypergraph with vertices as universe elements, and then following the Domatic Partition problem. But as far as I understand the above paper works for graphs and not hypergraphs. $\endgroup$ May 29, 2013 at 11:17
-
$\begingroup$ You have look in the paper and see the randomized algorithm that gives the result for domatic paper and adapt it for disjoint set covers. It is straight forward. There could be a direct reduction as well. $\endgroup$ May 30, 2013 at 17:18