
doi: 10.1051/ro:2006001
Summary: 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.
Combinatorial optimization, bin covering problem, online approximation algorithm, Inventory, storage, reservoirs, Approximation algorithms, bin packing problem, uniform sized bins, asymptotic worst case ratio, Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.), longest item
Combinatorial optimization, bin covering problem, online approximation algorithm, Inventory, storage, reservoirs, Approximation algorithms, bin packing problem, uniform sized bins, asymptotic worst case ratio, Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.), longest item
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 9 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 10% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
