Quasi-Polynomial Time Approximation Scheme for Weighted Geometric Set Cover on Pseudodisks and Halfspaces
Nabil H. Mustafa, Rajiv Raman, Saurabh Ray · SIAM Journal on Computing · 2015
Weighted geometric set-cover problems arise naturally in several geometric and nongeometric settings (e.g., the breakthrough of Bansal and Pruhs [Proceedings of FOCS, 2010, pp. 407--414] reduces a wide class of machine scheduling problems to weighted geometric set cover). More than two decades of research has succeeded in settling the $(1+\epsilon)$-approximability status for most geometric set-cover problems, except for some basic scenarios which are still lacking. One is that of weighted disks in the plane for which, after a series of papers, Varadarajan [Proceedings of STOC'10, 2010, pp. 641--648] presented a clever quasi-sampling technique, which together with improvements by Chan et al. [Proceedings of SODA, 2012, pp. 1576--1585], yielded an $O(1)$-approximation algorithm. Even for the unweighted case, a polynomial time approximation scheme (PTAS) for a fundamental class of objects called pseudodisks (which includes halfspaces, disks, unit-height rectangles, translates of convex sets, etc.) is currently unknown. Another fundamental case is weighted halfspaces in $\mathfrak{R}^3$, for which a PTAS is currently lacking. In this paper, we present a quasi PTAS (QPTAS) for all these remaining problems. Our results are based on the separator framework of Adamaszek and Wiese [Proceedings of FOCS, 2013, pp. 400--409; Proceedings of SODA, 2014, pp. 645--656], who recently obtained a QPTAS for a weighted independent set of polygonal regions. This rules out the possibility that these problems are APX-hard, assuming ${NP} ot\subseteq {DTIME}(2^{polylog(n)})$. Together with the recent work of Chan and Grant [Comput. Geom., 47 (2014), pp. 112--124], this settles the APX-hardness status for all natural geometric set-cover problems.