Improved Results on Geometric Hitting Set Problems

1. Agarwal, P.K., Mustafa, N.H.: Independent set of intersection graphs of convex objects in 2d. Comput. Geom. 34(2), 83–95 (2006)

   Article  MATH  MathSciNet  Google Scholar 

2. Ambühl, C., Erlebach, T., Mihalák, M., Nunkesser, M.: Constant-factor approximation for minimum-weight (connected) dominating sets in unit disk graphs. In: APPROX-RANDOM, pp. 3–14 (2006)

3. Arya, V., Garg, N., Khandekar, R., Meyerson, A., Munagala, K., Pandit, V.: Local search heuristic for k-median and facility location problems. In: STOC, pp. 21–29 (2001)

4. Bronnimann, H., Goodrich, M.: Almost optimal set covers in finite VC-dimension. Discrete Comput. Geom. 14(4), 463–479 (1995)

   Article  MathSciNet  Google Scholar 

5. Carmi, P., Katz, M., Lev-Tov, N.: Covering points by unit disks of fixed location. In: ISAAC, pp. 644–655 (2007)

6. Călinescu, G., Mandoiu, I.I., Wan, P.-J., Zelikovsky, A.Z.: Selecting forwarding neighbors in wireless ad hoc networks. Mob. Netw. Appl. 9(2), 101–111 (2004)

   Article  Google Scholar 

7. Chan, T., Har-Peled, S.: Approximation algorithms for maximum independent set of pseudo-disks. In: Proceedings of Symposium on Computational Geometry (2009)

8. Chan, T.M., Har-Peled, S.: Approximation algorithms for maximum independent set of pseudo-disks. In: Symposium on Computational Geometry, pp. 333–340 (2009)

9. Clarkson, K., Varadarajan, K.: Improved approximation algorithms for geometric set cover. Discrete Comput. Geom. 37, 43–58 (2007)

   Article  MATH  MathSciNet  Google Scholar 

10. Even, G., Rawitz, D., Shahar, S.: Hitting sets when the VC-dimension is small. Inf. Process. Lett. 95, 358–362 (2005)

    Article  MATH  MathSciNet  Google Scholar 

11. Frederickson, G.N.: Fast algorithms for shortest paths in planar graphs, with applications. SIAM J. Comput. 16(6), 1004–1022 (1987)

    Article  MATH  MathSciNet  Google Scholar 

12. Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, New York (1979)

    MATH  Google Scholar 

13. Haussler, D., Welzl, E.: Epsilon-nets and simplex range queries. Discrete Comput. Geom. 2, 127–151 (1987)

    Article  MATH  MathSciNet  Google Scholar 

14. Hochbaum, D.S., Maass, W.: Fast approximation algorithms for a nonconvex covering problem. J. Algorithms 8(3), 305–323 (1987)

    Article  MATH  MathSciNet  Google Scholar 

15. Kanungo, T., Mount, D.M., Netanyahu, N.S., Piatko, C.D., Silverman, R., Wu, A.Y.: A local search approximation algorithm for k-means clustering. In: Symposium on Computational Geometry, pp. 10–18 (2002)

16. Karp, R.M.: Reducibility among combinatorial problems. In: Miller, R.E., Thatcher, J.W. (eds.) Complexity of Computer Computations, pp. 85–103. Plenum, New York (1972)

    Google Scholar 

17. Lipton, R.J., Tarjan, R.E.: A separator theorem for planar graphs. Technical Report, Stanford University, Stanford, CA, USA (1977)

18. Matousek, J.: Lectures in Discrete Geometry. Springer, New York (2002)

    Google Scholar 

19. Matousek, J., Seidel, R., Welzl, E.: How to net a lot with little: Small epsilon-nets for disks and halfspaces. In: Proceedings of Symposium on Computational Geometry, pp. 16–22 (1990)

20. Mustafa, N., Ray, S.: Improved results on geometric hitting set problems. In: Proceedings of Symposium on Computational Geometry (2009)

21. Narayanappa, S., Vojtechovský, P.: An improved approximation factor for the unit disk covering problem. In: CCCG (2006)

22. Pach, J., Agarwal, P.K.: Combinatorial Geometry. Wiley, New York (1995)

    MATH  Google Scholar 

23. Pach, J., Woeginger, G.: Some new bounds for epsilon-nets. In: Symposium on Computational Geometry, pp. 10–15 (1990)

24. Pyrga, E., Ray, S.: New existence proofs for epsilon-nets. In: Proceedings of Symposium on Computational Geometry, pp. 199–207 (2008)

25. Raz, R., Safra, M.: A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP. In: Proceedings of STOC, pp. 475–484 (1997)

26. Varadarajan, K.: Weighted geometric set cover via quasi uniform sampling. In: STOC’ 10 Proceedings of the 42nd ACM Symposium on Theory of Computing, Cambridge, pp. 641–648. ACM, New York (2010)

    Chapter  Google Scholar 

Download references