# On the Partition Set Cover Problem

arXiv: https://arxiv.org/abs/1809.06506 · HTML: https://mlsanity.com/paper/1809.06506/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Sep 2018.

## Built on by (most cited first, 1 of 1)

- [Deploying Vaccine Distribution Sites for Improved Accessibility and Equity to Support Pandemic Response](https://mlsanity.com/paper/2202.04705/) (2022)

## Abstract (arXiv)

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.