Online LIB problems: Heuristics for Bin Covering and lower bounds for Bin Packing
RAIRO - Operations Research (2006)
- Volume: 39, Issue: 3, page 163-183
- ISSN: 0399-0559
Access Full Article
top
Abstract
topHow to cite
topFinlay, 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- S.F. Assmann, Problems in Discrete Applied Mathematics. Ph.D. thesis, Massachusetts Institute of Technology, Cambridge, MA (1983).
- 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.
- 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.
- 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.
- J. Csirik and J.B.G. Frenk, A Dual Version of Bin Packing. Algorithms Rev.1 (1990) 87–95.
- J. Csirik, J.B.G. Frenk, M. Labbe and S. Zhang, Two Simple Algorithms for Bin Covering. Acta Cybernetica14 (1999) 13–25.
- 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.
- 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.
- J. Csirik and V. Totik, On-line Algorithms for a Dual Version of Bin Packing. Discrete Appl. Math.21 (1988) 163–167.
- C.C. Lee and D.T. Lee, A Simple Online Bin Packing Algorithm. J. ACM32 (1985) 562–572.
- 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.
- 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.
- 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.
- A. Van Vliet, Optimal On-Line Algorithms For Variable-Sized Bin Covering. Inform. Process. Lett.43 (1992) 277–284.
- G.J. Woeginger and G. Zhang, Optimal On-Line Algorithms For Variable-Sized Bin Covering. Oper. Res. Lett.25 (1999) 47–50.
NotesEmbed ?
topYou must be logged in to post comments.
To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.