Proceedings of ISP RAS

Probabilistic analysis a algorithm for strip packing.

N.N.Kuzjurin, A.I. Pospelov.


In the article an on-line algorithm for packing rectangles into a strip is presented and studied. The estimation of expected wasted ratio for the algorithm is obtained.


Strip packing, probabilistic analysis, approximate algorithms.


Proceedings of the Institute for System Programming, vol. 19, 2010, pp. 157-164.

ISSN 2220-6426 (Online), ISSN 2079-8156 (Print).

Full text of the paper in pdf (in Russian) Back to the contents of the volume