Bin packing and covering with longest items at the bottom: online version


  • P. Manyem



We consider the NP hard problems of online bin packing and online bin covering 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. Bin sizes can be uniform or variable. If variable, the bin sizes are drawn from a finite collection. In uniform sized online bin packing, we prove an upper bound of two on the approximation ratio for special cases of the problem and provide computational results for the general case using a variation of the first fit heuristic. In uniform sized online bin covering, we prove a non-approximability result and present a modified first fit heuristic. In online variable-sized bin covering, we show that the approximation ratio guaranteed by our heuristic is a function of bin lengths.





Articles for Electronic Supplement