Online LIB problems: Heuristics for Bin Covering and lower bounds for Bin Packing

Luke Finlay; Prabhu Manyem

RAIRO - Operations Research (2006)

  • Volume: 39, Issue: 3, page 163-183
  • ISSN: 0399-0559

Abstract

top
We consider the NP Hard problems of online Bin Covering and Packing while requiring that larger (or longer, in the one dimensional case) items be placed at the bottom of the bins, below smaller (or shorter) items — we call such a version, the LIB version of problems. Bin sizes can be uniform or variable. We look at computational studies for both the Best Fit and Harmonic Fit algorithms for uniform sized bin covering. The Best Fit heuristic for this version of the problem is introduced here. The approximation ratios obtained were well within the theoretical upper bounds. For variable sized bin covering, a more thorough analysis revealed definite trends in the maximum and average approximation ratios. Finally, we prove that for online LIB bin packing with uniform size bins, no heuristic can guarantee an approximation ratio better than 1.76 under the online model considered.

How to cite

top

Finlay, Luke, and Manyem, Prabhu. "Online LIB problems: Heuristics for Bin Covering and lower bounds for Bin Packing." RAIRO - Operations Research 39.3 (2006): 163-183. <http://eudml.org/doc/105329>.

@article{Finlay2006,
abstract = { We consider the NP Hard problems of online Bin Covering and Packing while requiring that larger (or longer, in the one dimensional case) items be placed at the bottom of the bins, below smaller (or shorter) items — we call such a version, the LIB version of problems. Bin sizes can be uniform or variable. We look at computational studies for both the Best Fit and Harmonic Fit algorithms for uniform sized bin covering. The Best Fit heuristic for this version of the problem is introduced here. The approximation ratios obtained were well within the theoretical upper bounds. For variable sized bin covering, a more thorough analysis revealed definite trends in the maximum and average approximation ratios. Finally, we prove that for online LIB bin packing with uniform size bins, no heuristic can guarantee an approximation ratio better than 1.76 under the online model considered. },
author = {Finlay, Luke, Manyem, Prabhu},
journal = {RAIRO - Operations Research},
keywords = {Online approximation algorithm; asymptotic worst case ratio; bin covering problem; bin packing problem; longest item; uniform sized bins.; online approximation algorithm; asymptotic worst case ratio; longest item; uniform sized bins},
language = {eng},
month = {1},
number = {3},
pages = {163-183},
publisher = {EDP Sciences},
title = {Online LIB problems: Heuristics for Bin Covering and lower bounds for Bin Packing},
url = {http://eudml.org/doc/105329},
volume = {39},
year = {2006},
}

TY - JOUR
AU - Finlay, Luke
AU - Manyem, Prabhu
TI - Online LIB problems: Heuristics for Bin Covering and lower bounds for Bin Packing
JO - RAIRO - Operations Research
DA - 2006/1//
PB - EDP Sciences
VL - 39
IS - 3
SP - 163
EP - 183
AB - We consider the NP Hard problems of online Bin Covering and Packing while requiring that larger (or longer, in the one dimensional case) items be placed at the bottom of the bins, below smaller (or shorter) items — we call such a version, the LIB version of problems. Bin sizes can be uniform or variable. We look at computational studies for both the Best Fit and Harmonic Fit algorithms for uniform sized bin covering. The Best Fit heuristic for this version of the problem is introduced here. The approximation ratios obtained were well within the theoretical upper bounds. For variable sized bin covering, a more thorough analysis revealed definite trends in the maximum and average approximation ratios. Finally, we prove that for online LIB bin packing with uniform size bins, no heuristic can guarantee an approximation ratio better than 1.76 under the online model considered.
LA - eng
KW - Online approximation algorithm; asymptotic worst case ratio; bin covering problem; bin packing problem; longest item; uniform sized bins.; online approximation algorithm; asymptotic worst case ratio; longest item; uniform sized bins
UR - http://eudml.org/doc/105329
ER -

References

top
  1. S.F. Assmann, Problems in Discrete Applied Mathematics. Ph.D. thesis, Massachusetts Institute of Technology, Cambridge, MA (1983).  
  2. S.F. Assmann, D.S. Johnson, D.J. Kleitman and J.Y.-T. Leung. On a Dual Version of the One-dimensional Bin Packing. J. Algorithms5 (1984) 502–525.  
  3. M. Carlyle, K. Knutson and J. Fowler, Bin covering algorithms in the second stage of the lot to order matching problem. J. Oper. Res. Soc.52 (2001) 1232–1243.  
  4. E.G. Coffman, M.R. Garey and D.S. Johnson, Bin Packing Approximation Algorithms: A Survey, in Approximation Algorithms for NP-Hard Problems edited by D. Hochbaum. PWS Publishing Company, Boston, MA (1997) 46–93.  
  5. J. Csirik and J.B.G. Frenk, A Dual Version of Bin Packing. Algorithms Rev.1 (1990) 87–95.  
  6. J. Csirik, J.B.G. Frenk, M. Labbe and S. Zhang, Two Simple Algorithms for Bin Covering. Acta Cybernetica14 (1999) 13–25.  
  7. J. Csirik, D.S. Johnson and C. Kenyon, Better approximation algorithms for bin covering, in SODA 2001: Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms (2001) 557–566.  
  8. J. Csirik, D.S. Johnson, C. Kenyon, J.B. Orlin, P.W. Shor and R.R. Weber, On the sum-of-squares algorithm for bin packing, in ACM-STOC 2000: Proceedings of the 32nd ACM Symposium on the Theory of Computing (2000) 208–217.  
  9. J. Csirik and V. Totik, On-line Algorithms for a Dual Version of Bin Packing. Discrete Appl. Math.21 (1988) 163–167.  
  10. C.C. Lee and D.T. Lee, A Simple Online Bin Packing Algorithm. J. ACM32 (1985) 562–572.  
  11. P. Manyem, Bin packing and covering with longest items at the bottom: Online version, The ANZIAM Journal (formerly Journal of the Austral. Math. Soc., Series B)43(E) (June 2002) E186–E231.  
  12. P. Manyem. Uniform Sized Bin Packing and Covering: Online Version, in Topics in Industrial Mathematics, edited by J.C. Misra. Narosa Publishing House, New Delhi (2003) 447–485.  
  13. P. Manyem, R.L. Salt, and M.S. Visser, Lower Bounds and Heuristics for Online LIB Bin Packing and Covering, in Proceedings of the 13th Australasian Workshop on Combinatorial Algorithms (Fraser Island, Queensland, Australia) (July 2002) 11–42.  
  14. A. Van Vliet, Optimal On-Line Algorithms For Variable-Sized Bin Covering. Inform. Process. Lett.43 (1992) 277–284.  
  15. G.J. Woeginger and G. Zhang, Optimal On-Line Algorithms For Variable-Sized Bin Covering. Oper. Res. Lett.25 (1999) 47–50.  

NotesEmbed ?

top

You must be logged in to post comments.