An algorithm for Multiple Strip Package and its average case evaluation
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).
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)-13Full text of the paper in pdf (in Russian) Back to the contents of the volume