Анализ некоторых эвристик в задаче упаковки прямоугольников в несколько полос.

Анализ некоторых эвристик в задаче упаковки прямоугольников в несколько полос.

С.Н. Жук.

Аннотация

Статья посвящена анализу некоторых эвристик в задаче упаковки прямоугольников в несколько полос. Предложен эффективный алгоритм, который размещает прямоугольники по полосам в онлайновом режиме и гарантирует константную мультипликативную точность. Это достигнуто за счёт правильной формализации понятии «допустимая полоса для прямоугольника». Показано, также, что полученная оценка точности достижима на некоторых исходных данных.

Издание

Труды Института системного программирования РАН, том 6, 2004, стр. 13-26.

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

Для цитирования

С.Н. Жук. Анализ некоторых эвристик в задаче упаковки прямоугольников в несколько полос. . Труды Института системного программирования РАН, том 6, 2004, стр. 13-26. .

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