Geodesic
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

Voir la notice de l'article provenant de la source Numdam

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
Keywords: 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://geodesic.mathdoc.fr/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://geodesic.mathdoc.fr/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://geodesic.mathdoc.fr/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

Cité par Sources :