On the Partition Set Cover Problem

Abstract

Several algorithms with an approximation guarantee of $O(\log n)$ are known for the Set Cover problem, where $n$ is the number of elements. We study a generalization of the Set Cover problem, called the Partition Set Cover problem. Here, the elements are partitioned into $r$ \emph{color classes}, and we are required to cover at least $k_t$ elements from each color class ${\mathcal{C}}_t$, using the minimum number of sets. We give a randomized LP-rounding algorithm that is an $O(\beta +\log r)$ approximation for the Partition Set Cover problem. Here $\beta$ denotes the approximation guarantee for a related Set Cover instance obtained by rounding the standard LP. As a corollary, we obtain improved approximation guarantees for various set systems for which $\beta$ is known to be sublogarithmic in $n$. We also extend the LP rounding algorithm to obtain $O(\log r)$ approximations for similar generalizations of the Facility Location type problems. Finally, we show that many of these results are essentially tight, by showing that it is NP-hard to obtain an $o(\log r)$-approximation for any of these problems.