On Geometric Priority Set Cover Problems

Aritra Banik, Rajiv Raman, Saurabh Ray

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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.

Original languageEnglish (US)
Title of host publication32nd International Symposium on Algorithms and Computation, ISAAC 2021
EditorsHee-Kap Ahn, Kunihiko Sadakane
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959772143
StatePublished - Dec 1 2021
Event32nd International Symposium on Algorithms and Computation, ISAAC 2021 - Fukuoka, Japan
Duration: Dec 6 2021Dec 8 2021

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
ISSN (Print)1868-8969


Conference32nd International Symposium on Algorithms and Computation, ISAAC 2021


  • Approximation algorithms
  • Geometric set cover
  • Local search
  • Quasi-uniform sampling

ASJC Scopus subject areas

  • Software


Dive into the research topics of 'On Geometric Priority Set Cover Problems'. Together they form a unique fingerprint.

Cite this