On the geometric priority set cover problem

• Published in: Computational geometry : theory and applications 2023-06, Vol.112, p.101984, Article 101984
• Main Authors: Banik, Aritra, Raman, Rajiv, Ray, Saurabh
• Format: Article
• Language: English
• Subjects: Approximation algorithms; Geometric set cover; Local search; Quasi-uniform sampling
• ISSN: 0925-7721
• DOI: 10.1016/j.comgeo.2023.101984

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.