This article is cited in 6 papers

Probabilistic analysis of a new class of strip packing algorithms

N. N. Kuzyurin, A. I. Pospelov

Institute for System Programming, Russian Academy of Sciences, ul. Solzhenitsyna 25, Moscow, 109004 Russia

Abstract: A new class of algorithms for online packing of rectangles into a strip is proposed and studied. It is proved that the expectation of the unfilled area for this class of algorithms is $O(N^{2/3})$ in the standard (for this type of problems) probabilistic model for $N$ random rectangles.

Key words: strip packing, probabilistic analysis, approximate algorithms.

UDC: 519.7

Received: 11.06.2010

 English version: Computational Mathematics and Mathematical Physics, 2011, 51:10, 1817–1822

Bibliographic databases:

• 
• 
•