Preview

Труды Института системного программирования РАН

Расширенный поиск

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

https://doi.org/10.15514/ISPRAS-2017-29(6)-13

Полный текст:

Аннотация

В 2012 году М. А. Трушников предложил принципиально новый онлайновый алгоритм упаковки прямоугольников в полосу, а в 2013 году в [3] была получена оценка точности алгоритма в среднем, равной математическому ожиданию незаполненной прямоугольниками площади, равная . Ранее известная оценка была существенно улучшена. В настоящей работе данная оценка улучшена до , а также алгоритм Трушникова обобщён на случай упаковки прямоугольников в полос, , с сохранением оценки .

Об авторах

Д. О. Лазарев
Московский физико-технический институт
Россия


Н. Н. Кузюрин
Московский физико-технический институт; Институт системного программирования им. В.П. Иванникова РАН
Россия


Список литературы

1. Coffman E.G., Jr, Shor P.W. Packing in two dimensions: Asymptotic average-case analysis of algotithms. Algorithmica, vol. 9, No 3, pp. 253-277

2. М.А. Трушников. Об одной задаче Коффмана-Шора, связанной с упаковкой прямоугольников в полосу. Труды ИСП РАН, том 22, 2012, стр. 456-462. DOI: 10.15514/ISPRAS-2012-22-24

3. М.А. Трушников. Вероятностный анализ нового алгоритма упаковки прямоугольников в полосу. Труды ИСП РАН, том 24, 2013, стр. 457-468, DOI: 10.15514/ISPRAS-2013-24-21

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


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


Лазарев Д.О., Кузюрин Н.Н. Алгоритм упаковки прямоугольников в несколько полос и анализ его точности в среднем. Труды Института системного программирования РАН. 2017;29(6):221-228. https://doi.org/10.15514/ISPRAS-2017-29(6)-13

For citation:


Lazarev D.O., Kuzyrin N.N. An algorithm for Multiple Strip Package and its average case evaluation. Proceedings of the Institute for System Programming of the RAS (Proceedings of ISP RAS). 2017;29(6):221-228. (In Russ.) https://doi.org/10.15514/ISPRAS-2017-29(6)-13

Просмотров: 73


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


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