 |
||||||||
| Volume 3, Number 3, September 2007, pp. 511-527 | ||||||||
| J.Y. Lin, P. Manyem and R.L. Sheu | ||||||||
| Key words: | ||||||||
| online approximation algorithm, asymptotic worst case ratio, bin packing problem, longest item, uniform sized bins, variable sized bins | ||||||||
| Mathematices Subject Classification: 68W25, 68Q17, 90B05, 90C27 | ||||||||
|
||||||||||||||||||||||||||||||||||||||||
| Abstract: | |||
| We consider the NP Hard problem of online Bin Packing while requiring that larger (or longer) items be placed below smaller (or shorter) items --- we call such a version the {LIB} version of problems. Bin sizes can be uniform or variable. We provide analytical upper bounds as well as experimental results on the asymptotic approximation ratio for the first fit algorithm. | |||
| Performance estimations of first fit algorithm for online bin packing with variable bin sizes and LIB constraints | ||