An algorithm for Multiple Strip Package and its average case evaluation
https://doi.org/10.15514/ISPRAS-2017-29(6)-13
Abstract
In 2012 M.A. Trushnikov in [2] 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 in [3] the average case evaluation for this method was attained and it equaled . The best known before evaluation was improved. In present article this evaluation was improved to . Also a new method was constructed for MSP Problem, where rectangles are packed in strips, , with average case evaluation equaling
About the Authors
D. O. Lazarev
Moscow Institute of Physics and Technology
Russian Federation
Russian Federation
N. N. Kuzyrin
Moscow Institute of Physics and Technology; Ivannikov Institute for System Programming of the Russian Academy of Sciences
Russian Federation
Russian Federation
References
1. Coffman E.G., Jr, Shor P.W. Packing in two dimensions: Asymptotic average-case analysis of algotithms. Algorithmica, vol. 9, No 3, pp. 253-277
2. M. A. Trushnikov. On one problem of Koffman-Shor connected to strip packing problem. Trudy ISP RAN/Proc. ISP RAS, vol. 22, 2012, pp. 456-462 (in Russian). DOI: 10.15514/ISPRAS-2012-22-24
3. M. A. Trushnikov. Probabilistic analysis of a new strip packing algorithm. Trudy ISP RAN/Proc. ISP RAS, vol. 24, 2013, pp. 457-468 (in Russian). DOI: 10.15514/ISPRAS-2013-24-21
4. S.N. Zhuk. Analysis of some heuristics in Multiple Strip Package Problem. Trudy ISP RAN/Proc. ISP RAS, vol. 6, 2004, pp. 13-26 (in Russian)
Review
For citations:
Lazarev D.O., Kuzyrin N.N. An algorithm for Multiple Strip Package and its average case evaluation. Proceedings of the Institute for System Programming of the RAS (Proceedings of ISP RAS). 2017;29(6):221-228. (In Russ.) https://doi.org/10.15514/ISPRAS-2017-29(6)-13
Email this article 