3
$\begingroup$

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 ?

$\endgroup$
3
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\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$ – user16200 May 29 '13 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$ – Chandra Chekuri May 30 '13 at 17:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.