Сборники трудов ИСП РАН


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

М.А. Трушников.

Аннотация

В 1993 году Коффман и Шор предложили онлайновый алгоритм упаковки прямоугольников в полосу с оценкой O(n^{2/3}) для математического ожидания незаполненной площади полосы в стандартной вероятностной модели. С тех пор вопрос о возможности улучшения этой оценки в классе онлайновых алгоритмов оставался открытым. В данной работе проанализирован принципиально новый онлайновый алгоритм упаковки, предложенный ранее автором. Для него доказана оценка O(n^{1/2} (\log n)^{3/2}) для математического ожидания незаполненной площади полосы.

Ключевые слова

онлайновый алгоритм упаковки, вероятностный анализ качества упаковки

Издание

Труды Института системного программирования РАН, том 24, 2013, стр. 457-468.

ISSN 2220-6426 (Online), ISSN 2079-8156 (Print).

DOI: 10.15514/ISPRAS-2013-24-21

Полный текст статьи в формате pdf Вернуться к содержанию тома