License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SoCG.2018.47
URN: urn:nbn:de:0030-drops-87607
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8760/
Go to the corresponding LIPIcs Volume Portal

Inamdar, Tanmay ; Varadarajan, Kasturi

On Partial Covering For Geometric Set Systems

pdf-format:
LIPIcs-SoCG-2018-47.pdf (0.5 MB)

Abstract

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.

BibTeX - Entry

@InProceedings{inamdar_et_al:LIPIcs:2018:8760,
  author =	{Tanmay Inamdar and Kasturi Varadarajan},
  title =	{{On Partial Covering For Geometric Set Systems}},
  booktitle =	{34th International Symposium on Computational Geometry (SoCG 2018)},
  pages =	{47:1--47:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-066-8},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{99},
  editor =	{Bettina Speckmann and Csaba D. T{\'o}th},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/8760},
  URN =		{urn:nbn:de:0030-drops-87607},
  doi =		{10.4230/LIPIcs.SoCG.2018.47},
  annote =	{Keywords: Partial Set Cover, Geometric Set Cover}
}

Keywords: Partial Set Cover, Geometric Set Cover
Collection: 34th International Symposium on Computational Geometry (SoCG 2018)
Issue Date: 2018
Date of publication: 08.06.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI