Preprint
On the Partition Set Cover Problem
ArXiv.org
09/17/2018
DOI: 10.48550/arxiv.1809.06506
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.
Details
- Title: Subtitle
- On the Partition Set Cover Problem
- Creators
- Tanmay InamdarKasturi Varadarajan
- Resource Type
- Preprint
- Publication Details
- ArXiv.org
- DOI
- 10.48550/arxiv.1809.06506
- ISSN
- 2331-8422
- Language
- English
- Date posted
- 09/17/2018
- Academic Unit
- Computer Science
- Record Identifier
- 9984411104202771
Metrics
1 Record Views