RUS  ENG
Полная версия
ЖУРНАЛЫ // Дискретная математика // Архив

Дискрет. матем., 2007, том 19, выпуск 4, страницы 117–131 (Mi dm981)

Эта публикация цитируется в 6 статьях

Об онлайн-алгоритмах упаковки прямоугольников в несколько полос

С. Н. Жук


Аннотация: Исследуется задача об упаковке прямоугольников в несколько полос. Показано, что для этой задачи существуют онлайн-алгоритмы с асимптотической мультипликативной ошибкой сколь угодно близкой к $2e$, где $e$ – основание натурального логарифма. Доказано, что ни один онлайн-алгоритм не может иметь асимптотическую мультипликативную ошибку меньше, чем $e$.

УДК: 519.7

Статья поступила: 16.01.2007

DOI: 10.4213/dm981


 Англоязычная версия: Discrete Mathematics and Applications, 2007, 17:5, 517–531

Реферативные базы данных:


© МИАН, 2024