Exact algorithms and APX-hardness results for geometric packing and covering problems

Agarwal, 2004, Lenses in arrangements of pseudo-circles and their applications, J. ACM, 51, 139, 10.1145/972639.972641 Alimonti, 2000, Some APX-completeness results for cubic graphs, Theoret. Comput. Sci., 237, 123, 10.1016/S0304-3975(98)00158-3 C. Ambühl, T. Erlebach, M. Mihalák, M. Nunkesser, Constant-factor approximation for minimum-weight (connected) dominating sets in unit disk graphs, in: APPROX and RANDOM, 2006, pp. 3–14. Aronov, 2010, Small-size ϵ-nets for axis-parallel rectangles and boxes, SIAM J. Comput., 39, 3248, 10.1137/090762968 N. Bansal, K. Pruhs, The geometry of scheduling, in: IEEE 51st Annual Symposium on Foundations of Computer Science, 2010, pp. 407–414. de Berg, 2008 Berman, 1997, Complexities of efficient solutions of rectilinear polygon cover problems, Algorithmica, 17, 331, 10.1007/BF02523677 Brönnimann Brönnimann, 1995, Almost optimal set covers in finite VC-dimension, Discrete Comput. Geom., 14, 263, 10.1007/BF02570718 D. Chakrabarty, E. Grant, J. Koenemann, On column-restricted and priority covering integer programs, in: Integer Programming and Combinatorial Optimization, 2010, pp. 355–368. T.M. Chan, E. Grant, Exact algorithms and APX-hardness results for geometric set cover, in: Proc. 23rd Canadian Conference on Computational Geometry, 2011, pp. 431–436. T.M. Chan, S. Har-Peled, Approximation algorithms for maximum independent set of pseudo-disks, in: Proc. 25th Annu. ACM Sympos. Comput. Geom., 2009, pp. 333–340. Clarkson, 2007, Improved approximation algorithms for geometric set cover, Discrete Comput. Geom., 37, 43, 10.1007/s00454-006-1273-8 Coxeter, 1969 Ene T. Erlebach, E.J. van Leeuwen, PTAS for weighted set cover on unit squares, in: APPROX and RANDOM, 2010, pp. 166–177. Even, 2005, Hitting sets when the VC-dimension is small, Inform. Process. Lett., 95, 358, 10.1016/j.ipl.2005.03.010 Har-Peled S. Har-Peled, M. Lee, Weighted geometric set cover problems revisited, Unpublished manuscript, 2008. Hochbaum, 1987, Fast approximation algorithms for a nonconvex covering problem, J. Algorithms, 8, 305, 10.1016/0196-6774(87)90012-5 E.J. van Leeuwen, Optimization and approximation on systems of geometric objects, Ph.D. thesis, Universiteit van Amsterdam, 2009. Mustafa, 2010, Improved results on geometric hitting set problems, Discrete Comput. Geom., 44, 883, 10.1007/s00454-010-9285-9 J. Pach, G. Tardos, Tight lower bounds for the size of epsilon-nets, in: Proc. 27th ACM Sympos. Comput. Geom., 2011, pp. 458–463. Papadimitriou, 1991, Optimization, approximation, and complexity classes, J. Comput. Syst. Sci., 43, 425, 10.1016/0022-0000(91)90023-X K. Varadarajan, Weighted geometric set cover via quasi-uniform sampling, in: ACM Symposium on Theory of Computing, 2010, pp. 641–648.