Отправить статью по E-mail On Online Algorithms for Bin, Strip, and Box Packing, and Their Worst-Case and Average-Case Analysis
- Авторы: Lazarev D.O.1,2, Kuzyurin N.N.1,2
-
Учреждения:
- Ivannikov Institute for System Programming, Russian Academy of Sciences
- Moscow Institute of Physics and Technology
- Выпуск: Том 45, № 8 (2019)
- Страницы: 448-457
- Раздел: Article
- URL: https://journals.rcsi.science/0361-7688/article/view/176974
- DOI: https://doi.org/10.1134/S0361768819080036
- ID: 176974
Цитировать
Открытый доступ
Доступ предоставлен
Только для подписчиков
Аннотация
In this survey, we consider online algorithms for bin packing and strip packing problems, as well as their generalizations (multidimensional bin packing, multiple strip packing, and packing into strips of different widths). For the latter problem, only the worst-case analysis is described; for the other problems, both the worst-case and average-case (probabilistic) asymptotic ratios are presented. The best lower and upper bounds are considered. Basic algorithms and methods for their analysis are discussed.
Об авторах
D. Lazarev
Ivannikov Institute for System Programming, Russian Academy of Sciences; Moscow Institute of Physics and Technology
Автор, ответственный за переписку.
Email: dennis810@mail.ru
Россия, ul. Solzhenitsyna 25, Moscow, 109004; Institutskii per. 9, Dolgoprudnyi, Moscow oblast, 141700
N. Kuzyurin
Ivannikov Institute for System Programming, Russian Academy of Sciences; Moscow Institute of Physics and Technology
Автор, ответственный за переписку.
Email: nnkuz@ispras.ru
Россия, ul. Solzhenitsyna 25, Moscow, 109004; Institutskii per. 9, Dolgoprudnyi, Moscow oblast, 141700
Дополнительные файлы
