Алгоритм упаковки прямоугольников в несколько полос и анализ его точности в среднем
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
Послать статью по эл. почте 