On Partial Covering For Geometric Set Systems

Abstract

We study a generalization of the Set Cover problem called the \emph{Partial Set Cover} in the context of geometric set systems. The input to this problem is a set system $(X,\mathcal{S})$, where $X$ is a set of elements and $\mathcal{S}$ is a collection of subsets of $X$, and an integer $k\le |X|$. The goal is to cover at least $k$ elements of $X$ by using a minimum-weight collection of sets from $\mathcal{S}$. The main result of this article is an LP rounding scheme which shows that the integrality gap of the Partial Set Cover LP is at most a constant times that of the Set Cover LP for a certain projection of the set system $(X,\mathcal{S})$. As a corollary of this result, we get improved approximation guarantees for the Partial Set Cover problem for a large class of geometric set systems.