Analysis of a first-fit algorithm for the capacitated unit covering problem

References

• P. Berman, J. Jeong, S.P. Kasiviswanathan, and B. Urgaonkar, Packing to angles and sectors, in Proceedings of the Nineteenth Annual ACM Symposium on Parallel Algorithms and Architectures, ACM, San Diego, CA, 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, in Proceedings of the 16th Annual International Conference on Computing and Combinatorics, Springer-Verlag, Nha Trang, Vietnam, 2010, pp. 226–234.
   Google Scholar
• J.O. Berkey and P.Y. Wang, Two-dimensional finite bin-packing algorithms, J. Oper. Res. Soc. 38 (1987), pp. 423–429.
   Web of Science ®Google Scholar
• F.R. Chung, M.R. Garey, and D.S. Johnson, On packing two-dimensional bins, SIAM J. Algebra. Discr. 3 (1982), pp. 66–76.
   Web of Science ®Google Scholar
• E.G. Coffman Jr, M.R. Garey, D.S. Johnson, and R.E. Tarjan, Performance bounds for level-oriented two-dimensional packing algorithms, SIAM J. Comput. 9 (1980), pp. 808–826.
   Web of Science ®Google Scholar
• E.G. Coffman Jr, M.R. Garey, and D.S. Johnson, Approximation algorithms for bin packing: a survey, in Approximation Algorithms for NP-hard Problems, PWS Publishing, Boston, MA, 1997, pp. 46–93.
   Google Scholar
• L. Epstein and A. Levin, On Bin Packing with Conflicts, in Approximation and Online Algorithms, Springer, Berlin/Heidelberg, 2007, pp. 160–173.
   Google Scholar
• L. Epstein, A. Levin, and R. van Stee, Online unit clustering: variations on a theme, Theor. Comput. Sci. 1 (2008), pp. 85–96.
   Web of Science ®Google Scholar
• G. Even, D. Rawitz, and S.M. Shahar, Hitting sets when the VC-dimension is small, Inform. Process. Lett. 95 (2005), pp. 358–362.
   Web of Science ®Google Scholar
• T. Feder and D. Greene, Optimal algorithms for approximate clustering, in Proceedings of the 20th Annual ACM Symposium on the Theory of Computing, 1988, pp. 434–444.
   Google Scholar
• M. Franceschetti, M. Cook, and J. Bruck, A geometric theorem for approximate disk covering algorithms, Report ETR035, Caltech, 2001.
   Google Scholar
• B. Fu, Z. Chen, and M. Abdelguerfi, An almost linear time 2.8334-approximation for the disc covering problem, in AAIM 2007, Springer, Portland, OR, 2007, pp. 317–326.
   Google Scholar
• M.R. Garey, R.L. Graham, D.S. Johnson, and A.C.C. Yao, Resource constrained scheduling as generalized bin packing, J. Comb. Theory A. 21 (1976), pp. 257–298.
   Web of Science ®Google Scholar
• T.F. Gonzalez, Covering a set of points in multidimensional space, Inform. Process. Lett. 40 (1991), pp. 181–188.
   Web of Science ®Google Scholar
• X. Han, C. Peng, D. Ye, D. Zhang, and Y. Lan, Dynamic bin packing with unit fraction items revisited, Inform. Process. Lett. 110 (2010), pp. 1049–1054.
   Web of Science ®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.
   Web of Science ®Google Scholar
• K. Jansen and S. Öhring, Approximation algorithms for time constrained scheduling, Inform. Comput. 132 (1995), pp. 143–157.
   Web of Science ®Google Scholar
• D.S. Johnson, Fast algorithms for bin packing, J. Comput. Syst. Sci. 8 (1974), pp. 272–314.
   Web of Science ®Google Scholar
• J.Y. Lin, P. Manyem, and R.L. Sheu, Performance estimations of first fit Algorithm for online bin packing with variable bin sizes and LIB constraints, Pacific J. Opt. 3 (2007), pp. 511–527.
   Google Scholar
• P. Manyem, Bin packing and covering with longest items at the bottom: online version, ANZIAM J. 43 (2002), pp. 186–231.
   Google Scholar
• D. Simchi-Levi, New worst case results for the bin-packing problem, Nav. Res. Logis. 41 (1994), pp. 579–585.
   Web of Science ®Google Scholar
• V.V. Vazirani, Approximation Algorithms, 3rd ed., Springer, New York, 2003.
   Google Scholar
• B. Xia and Z. Tan, Tighter bounds of the first fit algorithm for the bin-packing problem, Discrete Appl. Math. 158 (2010), pp. 1668–1675.
   Web of Science ®Google Scholar