An algorithm for Multiple Strip Package and its average case evaluation

In 2012 M.A. Trushnikov in [2] suggested a new online method for 2DSP Problem. The average case evaluation for a 2DSP algorithm equals the expected value of space of strip not filled with rectangles. In 2013 in [3] the average case evaluation for this method was attained and it equaled $O(\sqrt N(\ln N)^\frac 32)$. The best known before evaluation $O(N^\frac 23)$ was improved. In present article this evaluation was improved to $O(\sqrt N\ln N)$. Also a new method was constructed for MSP Problem, where $N$ rectangles are packed in $k$ strips, $k\leq\sqrt N$, with average case evaluation equaling $O(\sqrt N\ln N)$.