On on-line algorithms for Bin, Strip and Box Packing, and their worstand average-case analysis

Abstract

In this survey, online algorithms for such packing problems as Bin Packing, Strip Packing and their generalizations, such as Multidimensional Bin Packing, Multiple Strip Packing and packing into strips of different width were considered. For the latter problem only worst-case analysis was described, for all other problems, both worst-case and average case (probabilistic analysis) asymptotical ratios were considered. Both lower and upper bonds were described. Basic algorithms and methods for their analysis were considered. For worst-case analysis of the Bin Packing Problem it was shown that for any online algorithm R^∞≥1.540, and an algorithm with R^∞≤1.589 was obtained. Both approaches for analyzing the algorithm and obtaining the lower bonds were discussed. Also it was shown that First Fit algorithm for Bin Packing has asymptotical competitive ratio of 17/10. For average case analysis in the case when object’s sizes have a uniform distribution on [0,1] in open-end analysis a construction for obtaining both lower bound of W_ ^n= Ω(√(n ln⁡n )) and algorithm with W_ ^n= θ(√(n ln⁡n )) was shown. In the case of closed-end analysis an algorithm with W_ ^n= θ(√n) was described. For Multidimensional Bin Packing with d dimensions an algorithm with R_ ^∞=(П_∞ )^d, where П_∞≈1.691, was obtained. For average case analysis an algorithm with W_A^n=O(n^((d+1)/(d+2))) was shown. For worst-case analysis of Strip Packing Problem and Multiple Strip Packing Problem algorithms with R^∞≤1.589 were also obtained. For the closed-end average case analysis algorithms with W_ ^n= θ(√n ln⁡n) were described. For the open-end average case analysis of Strip Packing Problem an algorithm with W_ ^n= O(n^(2/3) ) was considered. For generalization of Multiple Strip Packing Problem, where strips have different widths, an online algorithm with R_ ^∞≤2e/r for any r<1, where e=2.718…, was described.