An improvement of previously known upper bound of Multiple Strip Packing problem and probabilistic analysis of algorithm in case of large number of strips given

In this article, an analog of previously proposed algorithm Limited Hash Packing for Multiple Strip Packing Problem is studied using probabilistic analysis. Limited Hash Packing is an on-line algorithm, which works in closed-end mode, knowing the number $N$ of rectangles it has to pack before knowing the heights and width of the first rectangle. The algorithm proposes that width and heights of all rectangles have a uniform on $[0,1]$ distribution and works in two stages. Firstly, it divides the $k$ strips into $d=\Theta(\max\{k,\sqrt N\})$ rectangular areas width of which equal $\frac id,\forall i=\overline{1,\dots,d}$ such that the sum space of all this areas equals the expected space of all rectangles, $\frac N4$. Secondly, it packs a rectangle area of minimal width, in which it fits, or, if rectangle doesn’t fit in any area, above all areas. It was shown, that for any number of strips $k$ and any number of rectangles $N$, the expected value of space not filled with rectangles of all strips from their lowest point to the highest point of the highest rectangle, $E(S_{sp})\le 6\sqrt{N\ln N}+3k$. It was also shown, that $E(S_{sp})\ge \frac k8 - \frac{\sqrt N}4$. This result proves that the previous bound is asymptotically tight in case when packing $N$ rectangles into $k\ge\sqrt{N\ln N}$ strips.