On the Partition Set Cover Problem
share
Various O( n) approximations 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 k_t elements from each color class C_t, using the minimum number of sets. We give a randomized LP rounding algorithm that is an O(β + 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.
READ FULL TEXT