Новости
24 Апреля, 2024
ИСП РАН и «Базис» расширяют работу по повышению безопасности российских облачных решений
12 Апреля, 2024
Защита диссертаций
15 Марта, 2024
Сегодня стартовали выборы Президента России
Вероятностный анализ различных шельфовых алгоритмов упаковки прямоугольников в полосу.
Аннотация
Рассматривается задача упаковки множества прямоугольников в вертикальную полосу (strip packing problem). Изучается важный подкласс онлайновых алгоритмов для этой задачи – так называемые шельфовые алгоритмы. Предложен общий метод вероятностного анализа шельфовых алгоритмов, позволяющий для многих шельфовых алгоритмов оценивать математическое ожидание незаполненной площади, в предположении, что высота и ширина каждого прямоугольника являются случайными величинами.
Издание
Труды Института системного программирования РАН, том 12, 2007, стр. 17-26.
ISSN 2220-6426 (Online), ISSN 2079-8156 (Print).