An algorithm for Multiple Strip Package and its average case evaluation

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

Keywords

• новая эвристика
• задача упаковки прямоугольников в полосу
• задача упаковки прямоугольников в несколько полос
• оценка в среднем