Вероятностный анализ шельфовых алгоритмов упаковки прямоугольников в полосу

Работа посвящена анализу точности приближенных алгоритмов упаковки прямоугольников в полосу. Главным результатом является построение алгоритма, который размещает прямоугольники по мере поступления и для которого отношение математического ожидания незаполненной площади к математическому ожиданию заполненной площади стремится к нулю с ростом числа прямоугольников.
Работа выполнена при поддержке Российского фонда фундаментальных исследований, проекты 05–01–00798 и 04–01–00359.