Online LIB problems : heuristics for bin covering and lower bounds for bin packing
RAIRO - Operations Research - Recherche Opérationnelle, Tome 39 (2005) no. 3, pp. 163-183.

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.

DOI : 10.1051/ro:2006001
Classification : 68W25, 68Q17, 90B05, 90C27
Mots-clés : online approximation algorithm, asymptotic worst case ratio, bin covering problem, bin packing problem, longest item, uniform sized bins 
@article{RO_2005__39_3_163_0,
     author = {Finlay, Luke and Manyem, Prabhu},
     title = {Online {LIB} problems : heuristics for bin covering and lower bounds for bin packing},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {163--183},
     publisher = {EDP-Sciences},
     volume = {39},
     number = {3},
     year = {2005},
     doi = {10.1051/ro:2006001},
     mrnumber = {2205669},
     zbl = {1101.68982},
     language = {en},
     url = {http://archive.numdam.org/articles/10.1051/ro:2006001/}
}
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 - Recherche Opérationnelle
PY  - 2005
SP  - 163
EP  - 183
VL  - 39
IS  - 3
PB  - EDP-Sciences
UR  - http://archive.numdam.org/articles/10.1051/ro:2006001/
DO  - 10.1051/ro:2006001
LA  - en
ID  - RO_2005__39_3_163_0
ER  - 
%0 Journal Article
%A Finlay, Luke
%A Manyem, Prabhu
%T Online LIB problems : heuristics for bin covering and lower bounds for bin packing
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 2005
%P 163-183
%V 39
%N 3
%I EDP-Sciences
%U http://archive.numdam.org/articles/10.1051/ro:2006001/
%R 10.1051/ro:2006001
%G en
%F RO_2005__39_3_163_0
Finlay, Luke; Manyem, Prabhu. Online LIB problems : heuristics for bin covering and lower bounds for bin packing. RAIRO - Operations Research - Recherche Opérationnelle, Tome 39 (2005) no. 3, pp. 163-183. doi : 10.1051/ro:2006001. http://archive.numdam.org/articles/10.1051/ro:2006001/

[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. Algorithms 5 (1984) 502-525. | Zbl

[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 Cybernetica 14 (1999) 13-25. | Zbl

[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. | Zbl

[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. | Zbl

[10] C.C. Lee and D.T. Lee, A Simple Online Bin Packing Algorithm. J. ACM 32 (1985) 562-572. | MR | Zbl

[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. | MR | Zbl

[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. | MR | Zbl

[15] G.J. Woeginger and G. Zhang, Optimal On-Line Algorithms For Variable-Sized Bin Covering. Oper. Res. Lett. 25 (1999) 47-50. | MR | Zbl

Cité par Sources :