Улучшение ранее известной верхней оценки для задачи Multiple Strip Packing и вероятностный анализ алгоритма для большого числа полос

В работе рассмотрена задача упаковки прямоугольников в полосы единичной ширины Multiple Strip Packing. Рассмотрен аналог ранее предложенного алгоритма, алгоритм упаковки в области ограниченной высоты Limited Hash Packing и произведён его вероятностный анализ. Алгоритм онлайновый и работает в режиме closed-end, когда число прямоугольников, которые нужно упаковать известно алгоритму до начала работы. Лучшая из ранее известных оценок для математического ожидания площади полос, не заполненной прямоугольниками для задачи Multiple Strip Packing при числе полос $k\le\sqrt N$, составляющая $E(S_{sp})=O(\sqrt N\ln N)$ была улучшена до $E(S_{sp})=O(\sqrt{N\ln N})$. Также был произведён анализ алгоритма в случае $k=\omega(\sqrt N)$. Было доказано, что при любых $k, N$ выполнено $E(S_{sp})\ge \frac k8 - \frac{\sqrt N}4$.