Уточнённые оценки для алгоритмов упаковки $2$-гистограмм в полосу

Рассматривается NP-трудная задача, в которой требуется упаковать гистограммы из двух столбиков в полосу минимальной длины единичной высоты. Высота каждого столбика положительная и не превосходит $1$. Эта задача, называемая в англоязычной литературе Two-Bar Charts Packing Problem, является обобщением задачи упаковки в контейнеры и задачи двумерной векторной упаковки. Доказываются уточнённые оценки точности и трудоёмкости для некоторых ранее разработанных приближённых полиномиальных алгоритмов для Two-Bar Charts Packing Problem и её частных случаев. Показана достижимость этих оценок. Кроме того, рассматривается задача упаковки неограниченного числа гистограмм $k$ различных типов. При этом оценивается не длина упаковки, а её плотность, и предлагается полиномиальный алгоритм решения последней задачи в случае $k = \text{const}.$ Ил. 12, библиогр. 26.