License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ISAAC.2021.12
URN: urn:nbn:de:0030-drops-154459
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/15445/
Go to the corresponding LIPIcs Volume Portal

Banik, Aritra ; Raman, Rajiv ; Ray, Saurabh

On Geometric Priority Set Cover Problems

pdf-format:
LIPIcs-ISAAC-2021-12.pdf (0.7 MB)

Abstract

We study the priority set cover problem for simple geometric set systems in the plane. For pseudo-halfspaces in the plane we obtain a PTAS via local search by showing that the corresponding set system admits a planar support. We show that the problem is APX-hard even for unit disks in the plane and argue that in this case the standard local search algorithm can output a solution that is arbitrarily bad compared to the optimal solution. We then present an LP-relative constant factor approximation algorithm (which also works in the weighted setting) for unit disks via quasi-uniform sampling. As a consequence we obtain a constant factor approximation for the capacitated set cover problem with unit disks. For arbitrary size disks, we show that the problem is at least as hard as the vertex cover problem in general graphs even when the disks have nearly equal sizes. We also present a few simple results for unit squares and orthants in the plane.

BibTeX - Entry

@InProceedings{banik_et_al:LIPIcs.ISAAC.2021.12,
  author =	{Banik, Aritra and Raman, Rajiv and Ray, Saurabh},
  title =	{{On Geometric Priority Set Cover Problems}},
  booktitle =	{32nd International Symposium on Algorithms and Computation (ISAAC 2021)},
  pages =	{12:1--12:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-214-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{212},
  editor =	{Ahn, Hee-Kap and Sadakane, Kunihiko},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/15445},
  URN =		{urn:nbn:de:0030-drops-154459},
  doi =		{10.4230/LIPIcs.ISAAC.2021.12},
  annote =	{Keywords: Approximation algorithms, geometric set cover, local search, quasi-uniform sampling}
}

Keywords: Approximation algorithms, geometric set cover, local search, quasi-uniform sampling
Collection: 32nd International Symposium on Algorithms and Computation (ISAAC 2021)
Issue Date: 2021
Date of publication: 30.11.2021

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