  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.

Data Structures and Algorithms