TY - GEN
T1 - Settling the APX-hardness status for geometric set cover
AU - Mustafa, Nabil H.
AU - Raman, Rajiv
AU - Ray, Saurabh
N1 - Publisher Copyright:
© 2014 IEEE.
PY - 2014/12/7
Y1 - 2014/12/7
N2 - Weighted geometric set-cover problems arise naturally in several geometric and non-geometric settings (e.g. The breakthrough of Bansal and Pruhs (FOCS 2010) 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+ε)-approximability status for most geometric set-cover problems, except for four basic scenarios which are still lacking. One is that of weighted disks in the plane for which, after a series of papers, Varadarajan (STOC 2010) presented a clever quasi-sampling technique, which together with improvements by Chan et al(SODA 2012), yielded a O(1)-approximation algorithm. Even for the unweighted case, a PTAS for a fundamental class of objects called pseudodisks (which includes disks, unit-height rectangles, translates of convex sets etc.) is currently unknown. Another fundamental case is weighted halfspaces in R3, for which a PTAS is currently lacking. In this paper, we present a QPTAS for all of these remaining problems. Our results are based on the separator framework of Adamaszek and Wiese (FOCS 2013, SODA 2014), who recently obtained a QPTAS for weighted independent set of polygonal regions. This rules out the possibility that these problems are APX-hard, assuming NP DTIME(2polylog(n)). Together with the recent work of Chan-Grant (CGTA 2014), this settles the APX-hardness status for all natural geometric set-cover problems.
AB - Weighted geometric set-cover problems arise naturally in several geometric and non-geometric settings (e.g. The breakthrough of Bansal and Pruhs (FOCS 2010) 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+ε)-approximability status for most geometric set-cover problems, except for four basic scenarios which are still lacking. One is that of weighted disks in the plane for which, after a series of papers, Varadarajan (STOC 2010) presented a clever quasi-sampling technique, which together with improvements by Chan et al(SODA 2012), yielded a O(1)-approximation algorithm. Even for the unweighted case, a PTAS for a fundamental class of objects called pseudodisks (which includes disks, unit-height rectangles, translates of convex sets etc.) is currently unknown. Another fundamental case is weighted halfspaces in R3, for which a PTAS is currently lacking. In this paper, we present a QPTAS for all of these remaining problems. Our results are based on the separator framework of Adamaszek and Wiese (FOCS 2013, SODA 2014), who recently obtained a QPTAS for weighted independent set of polygonal regions. This rules out the possibility that these problems are APX-hard, assuming NP DTIME(2polylog(n)). Together with the recent work of Chan-Grant (CGTA 2014), this settles the APX-hardness status for all natural geometric set-cover problems.
KW - Hitting Sets
KW - Pseudodisks
KW - Quasi PTAS
KW - k-admissible regions
UR - http://www.scopus.com/inward/record.url?scp=84920025974&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84920025974&partnerID=8YFLogxK
U2 - 10.1109/FOCS.2014.64
DO - 10.1109/FOCS.2014.64
M3 - Conference contribution
AN - SCOPUS:84920025974
T3 - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
SP - 541
EP - 550
BT - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
PB - IEEE Computer Society
T2 - 55th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2014
Y2 - 18 October 2014 through 21 October 2014
ER -