2026-07-22T18:45:16Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8760 2024-03-06T10:42:35Z ddc:004 open_access

On Partial Covering For Geometric Set Systems Inamdar, Tanmay Varadarajan, Kasturi Partial Set Cover Geometric Set Cover We study a generalization of the Set Cover problem called the Partial Set Cover in the context of geometric set systems. The input to this problem is a set system (X, R), where X is a set of elements and R is a collection of subsets of X, and an integer k <= |X|. Each set in R has a non-negative weight associated with it. The goal is to cover at least k elements of X by using a minimum-weight collection of sets from R. 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, R). 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Tanmay Inamdar and Kasturi Varadarajan 2018 Is Part Of LIPIcs, Volume 99, 34th International Symposium on Computational Geometry (SoCG 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2018.47 urn:nbn:de:0030-drops-87607 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.47 eng https://creativecommons.org/licenses/by/3.0/legalcode