Proceedings of ISP RAS

An algorithm for Multiple Strip Package and its average case evaluation

Lazarev D.O. (MIPT, Dolgoprudny, Moscow Region, Russia)
Kuzyrin N.N. (ISP RAS, Moscow, Russia; MIPT, Dolgoprudny, Moscow Region, Russia)


In 2012 M.A. Trushnikov 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 the average case evaluation for this method was attained and it equaled O(√N(lnN)^(3/2)). The best known before evaluation O(N^(2/3)) was improved. In present article this evaluation was improved to O(√N lnN). Also a new method was constructed for MSP Problem, where N rectangles are packed in k strips, k≤√N, with average case evaluation equaling O(√N lnN).


new heuristic, Strip Packing problem, Multiple Strip Packing problem, average case evaluation


Proceedings of the Institute for System Programming, vol. 29, issue 6, 2017, pp. 221-228.

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

DOI: 10.15514/ISPRAS-2017-29(6)-13

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