Improved Algorithms for Minimum-Membership Geometric Set Cover

Bandyapadhyay et al. introduced the generalized minimum-membership geometric set cover (GMMGSC) problem [SoCG, 2023], which is defined as follows: We are given two sets P and \(P'\) of points in \(\mathbb {R}^{2}\) , \(n=\max (|P|, |P'|)\) , and a set \(\mathcal {S}\) of m axis-parallel unit squares. The goal is to find a subset \(\mathcal {S}^{*}\subseteq \mathcal {S}\) that covers all the points in P while minimizing \(\textsf{memb}(P', \mathcal {S}^{*})\) , where \(\textsf{memb}(P', \mathcal {S}^{*})=\max _{p\in P'}|\{s\in \mathcal {S}^{*}: p\in s\}|\) . We study GMMGSC problem and give a 16-approximation algorithm that runs in \(O(m^2\log m + m^2n)\) time. Our result is a significant improvement to the 144-approximation given by Bandyapadhyay et al. that runs in \(\tilde{O}(nm)\) time. GMMGSC problem is a generalization of another well-studied problem called Minimum Ply Geometric Set Cover (MPGSC), in which the goal is to minimize the ply of \(\mathcal {S}^{*}\) , where the ply is the maximum cardinality of a subset of the unit squares that have a non-empty intersection. The best-known result for the MPGSC problem is an 8-approximation algorithm by Durocher et al. that runs in \(O(n + m^{8}k^{4}\log k + m^{8}\log m\log k)\) time, where k is the optimal ply value [WALCOM, 2023].