Proceedings of ISP RAS


Probabilistic analysis a algorithm for strip packing.

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

Abstract

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.

Keywords

Strip packing, probabilistic analysis, approximate algorithms.

Edition

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