On the Partition Set Cover Problem

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 color classes, and we are required to cover at least kt elements from each color class Ct, using the minimum number of sets. We give a randomized LP-rounding algorithm that is an O(β + log r) approximation for the Partition Set Cover problem. Here β 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 β 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.