|
Эта публикация цитируется в 39 научных статьях (всего в 39 статьях)
Приближенные алгоритмы упаковки прямоугольников в несколько полос
С. Н. Жук
Аннотация:
Рассматривается задача упаковки прямоугольников в несколько полубесконечных полос определенной ширины. В работе предложены два достаточно просто реализуемых алгоритма, в которых прямоугольники размещаются по мере поступления. Показано, что точность первого алгоритма не аппроксимируется никакой абсолютной постоянной. Второй алгоритм гарантирует константную мультипликативную точность, причем доказанная оценка мультипликативной точности неулучшаема.
Работа выполнена при поддержке Российского фонда фундаментальных исследований, проект 05–01–00798.
Статья поступила: 26.01.2005
Образец цитирования:
С. Н. Жук, “Приближенные алгоритмы упаковки прямоугольников в несколько полос”, Дискрет. матем., 18:1 (2006), 91–105; Discrete Math. Appl., 16:1 (2006), 73–85
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/dm34https://doi.org/10.4213/dm34 https://www.mathnet.ru/rus/dm/v18/i1/p91
|
Статистика просмотров: |
Страница аннотации: | 1440 | PDF полного текста: | 756 | Список литературы: | 114 | Первая страница: | 2 |
|