On one problem of Koffman-Shor connected to strip packing problem
In 1993 Coffman and Shor proposed on-line strip packing algorithm with expected unpacked area (waste area) of order O(n^{2/3}) in a standard probabilistic model, where n is the number of rectangles. In the standard probabilistic model the width and height of each rectangle are independent random var...
| Главный автор: | |
|---|---|
| Формат: | Статья |
| Язык: | English |
| Опубликовано: |
Ivannikov Institute for System Programming of the Russian Academy of Sciences
2018-10-01
|
| Серии: | Труды Института системного программирования РАН |
| Предметы: | |
| Online-ссылка: | https://ispranproceedings.elpub.ru/jour/article/view/1022 |