On the geometric priority set cover problem

Aritra Banik, Rajiv Raman, Saurabh Ray

Research output: Contribution to journalArticlepeer-review


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)
Article number101984
JournalComputational Geometry: Theory and Applications
StatePublished - Jun 2023


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

ASJC Scopus subject areas

  • Computer Science Applications
  • Geometry and Topology
  • Control and Optimization
  • Computational Theory and Mathematics
  • Computational Mathematics


Dive into the research topics of 'On the geometric priority set cover problem'. Together they form a unique fingerprint.

Cite this