Приближенные алгоритмы упаковки прямоугольников в несколько полос

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