On on-line algorithms for Bin, Strip and Box packing, and their worst- and average-case analysis

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 bounds 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^\infty\ge 1.540$, and an algorithm with $R^\infty\le 1.589$ was obtained. Both approaches for analyzing the algorithm and obtaining the lower bounds were discussed. Also it was shown that First Fit algorithm for Bin Packing has asymptotical competitive ratio of $\frac{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=\Omega(\sqrt{n\ln n})$ and algorithm with $W^n=\theta(\sqrt{n\ln n})$ was shown. In the case of closed-end analysis an algorithm with $W^n=\theta(\sqrt n)$ was described. For Multidimensional Bin Packing with $d$ dimensions an algorithm with $R^\infty=(\Pi_\infty)^d$, where $\Pi_\infty\approx 1.691$, was obtained. For average case analysis an algorithm with $W_A^n=O(n^{\frac{d+1}{d+2}})$ was shown. For worst-case analysis of Strip Packing Problem and Multiple Strip Packing Problem algorithms with $R^\infty\le 1.589$ were also obtained. For the closed-end average case analysis algorithms with $W^n=\theta(\sqrt n \ln n)$ were described. For the open-end average case analysis of Strip Packing Problem an algorithm with $W^n=O(n^\frac 23)$ was considered. For generalization of Multiple Strip Packing Problem, where strips have different widths, an online algorithm with $R^\infty\le\frac{2e}r$ for any $r<1$, where $e=2.718\ldots$, was described.