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

News

02 August, 2019 OS DAY-2019. Cooperation among operating platform developers and the security of Russian software

10 April, 2019 Ivannikov Memorial Workshop has been supported by IEEE

14 March, 2019 The annual Ivannikov Memorial Workshop will take place on 13-14 September 2019

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

С.Н. Жук.

Abstract

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

Edition

Proceedings of the Institute for System Programming, vol. 6 (in Russian), 2004, Стр. 13-26.

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

For citation

С.Н. Жук. Анализ некоторых эвристик в задаче упаковки прямоугольников в несколько полос. . Proceedings of the Institute for System Programming, vol. 6 (in Russian), 2004, Стр. 13-26. .

Full text of the paper in pdf (in Russian)

Back to the contents of the volume