On capacitated covering with unit balls

References

• P.K. Agarwal and C.M. Procopiuc, Exact and approximation algorithms for clustering, Algorithmica 33 (2002), pp. 201–226. doi: 10.1007/s00453-001-0110-y
   Web of Science ®Google Scholar
• N. Bansal, J.R. Correa, C. Kenyon, and M. Sviridenko, Bin packing in multiple dimensions: In approximability results and approximation schemes, Math. Oper. Res. 31 (2006), pp. 31–49. doi: 10.1287/moor.1050.0168
   Web of Science ®Google Scholar
• N. Bansal, R. Krishnaswamy, and B. Saha, On capacitated set cover problems, in Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, Springer, Berlin, 2011, pp. 38–49.
   Google Scholar
• J. Bar-Ilan, G. Kortsarz, and D. Peleg, How to allocate network centers, J. Algorithms 15 (1993), pp. 385–415. doi: 10.1006/jagm.1993.1047
   Web of Science ®Google Scholar
• R. Bar-Yehuda, G Flysher, J. Mestre, and D. Rawitz, Approximation of partial capacitated vertex cover, in Algorithms -- ESA 2007, in Algorithms – ESA 2007, L. Arge, M. Hoffmann, E. Welzl, eds., Springer, Heidelbergh, 2007, pp. 335–346.
   Google Scholar
• P. Berman, J. Jeong, S.P. Kasiviswanathan, and B. Urgaonkar, Packing to angles and sectors, Proceedings of the Nineteenth Annual ACM Symposium on Parallel Algorithms and Architectures, ACM, San Diego, CA, USA, 2007, pp. 171–180.
   Google Scholar
• P. Berman, M. Karpinski, and A. Lingas, Exact and Approximation Algorithms for Geometric and Capacitated Set Cover Problems with Applications, 2009.
   Google Scholar
• H. Bronnimann and M.T. Goodrich, Almost optimal set covers in finite VC-dimension, Discret Comput. Geom. 14 (1995), pp. 463–479. doi: 10.1007/BF02570718
   Web of Science ®Google Scholar
• D. Chakrabarty, E. Grant, and J. Konemann, On Column-restricted and Priority Covering Integer Programs, IPCO'10, 2010, pp. 355–368.
   Google Scholar
• C. Chekuri and S. Khanna, On multi-dimensional packing problems, SIAM J. Comput. 33 (2004), pp. 837–851. doi: 10.1137/S0097539799356265
   Web of Science ®Google Scholar
• J.E.G. Coffman, M.R. Garey, and D.S. Johnson, Approximation algorithms for bin packing: A survey, in Approximation Algorithms for NP-hard Problems, D.S. Hochbaum, ed., PWS Publishing Co., Boston, MA, 1997, pp. 46–93.
   Google Scholar
• T.H. Cormen, C.E. Leiserson, R.L. Rivest, and C. Stein, Introduction to Algorithms, MIT Press, Cambridge, MA, 2001.
   Google Scholar
• L. Epstein and A. Levin, On bin packing with conflicts, in Approximation and Online Algorithms, T. Erlebach and C. Kaklamanis, eds., Springer, Berlin, 2007, pp. 160–173.
   Google Scholar
• L. Epstein, A. Levin, and R. Van Stee, Online unit clustering: Variations on a theme, Theoret. Comput. Sci. 1 (2008), pp. 85–96. doi: 10.1016/j.tcs.2008.04.046
   Web of Science ®Google Scholar
• T. Feder, and D. Greene, Optimal algorithms for approximate clustering, Proceedings of the 20th Annual ACM Symposium on the Theory of Computing, Chicago, Illinois, USA, 1988, pp. 434–444.
   Google Scholar
• R.J. Fowler, M.S. Paterson, and S.L. Tanimoto, Optimal packing and covering in the plane are NP-complete, Inf. Process. Lett. 3 (1981), pp. 133–137. doi: 10.1016/0020-0190(81)90111-3
   Web of Science ®Google Scholar
• M. Franceschetti, M. Cook, and J. Bruck, A geometric theorem for approximate disk covering algorithms, ETR035, Caltech, 2001.
   Google Scholar
• B. Fu, Z. Chen, and M. Abdelguer, An Almost Linear Time 2.8334-Approximation for the Disc Covering Problem, AAIM 2007, Springer, Portland, OR, 2007, pp. 317–326.
   Google Scholar
• M.R. Garey and D.S. Johnson, Computers and Intractability, A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1990.
   Google Scholar
• T.F. Gonzalez, Covering a set of points in multidimensional space, Inf. Process. Lett. 40 (1991), pp. 181–188. doi: 10.1016/0020-0190(91)90075-S
   Web of Science ®Google Scholar
• T.F. Gonzalez, The online D-dimensional dictionary problem, SODA '92 Proceedings of the Third Annual ACM-SIAM Symposium on Discrete Algorithms, Orlando, FL, United States, 1992, pp. 376–385.
   Google Scholar
• X. Han, K. Iwama, D. Ye, and G. Zhang, Strip packing vs. bin packing, in Algorithmic Aspects in Information and Management, M. Kao and X. Li, eds., Springer, Berlin, 2007, pp. 358–367.
   Google Scholar
• D.S. Hochbaum and W. Maass, Approximation schemes for covering and packing problems in image processing and VLSI, J. ACM 32 (1985), pp. 130–136. doi: 10.1145/2455.214106
   Web of Science ®Google Scholar
• K. Jansen and S. Ohring, Approximation algorithms for time constrained scheduling, Inf. Comput. 132 (1995), pp. 143–157.
   Web of Science ®Google Scholar
• D.S. Johnson, Fast algorithms for bin packing, Journal of Computer and System Sciences 8 (1974), pp. 272–314. doi: 10.1016/S0022-0000(74)80026-7
   Web of Science ®Google Scholar
• R.K. Madhukar, C.G. Plaxton, and R. Rajmohan, Analysis of a local search heuristic for facility location problems, Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics, San Francisco, CA, United States, 1998.
   Google Scholar
• D. Simchi-Levi, New worst case results for the bin-packing problem, Naval Res. Logist. 41 (1994), pp. 579–585. doi: 10.1002/1520-6750(199406)41:4<579::AID-NAV3220410409>3.0.CO;2-G
   Web of Science ®Google Scholar
• V.V. Vazirani, Approximation Algorithms, 3rd ed., Springer, New York, NY, 2003.
   Google Scholar
• L.A. Wolsey, An analysis of the greedy algorithm for the submodular set covering problem, Combinatorica 2 (1982), pp. 385–393. doi: 10.1007/BF02579435
   Web of Science ®Google Scholar