Logo image
Back
On Partial Covering For Geometric Set Systems
Conference proceeding   Open access

On Partial Covering For Geometric Set Systems

Tanmay Inamdar and Kasturi Varadarajan
Leibniz International Proceedings in Informatics, LIPIcs, Vol.99, pp.471-4714
11/13/2017
DOI: 10.4230/lipics.socg.2018.47
url
https://doi.org/10.4230/lipics.socg.2018.47View
Published (Version of record) Open Access

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.
 Algorithms Computational Geometry Computer Science Data Structures

Details

Metrics

6 Record Views
Logo image