Пожалуйста, используйте этот идентификатор, чтобы цитировать или ссылаться на этот документ:
https://elib.bsu.by/handle/123456789/264668
Заглавие документа: | Online bin stretching with bunch techniques |
Авторы: | Gabay, M. Kotov, V. Brauner, N. |
Тема: | ЭБ БГУ::ЕСТЕСТВЕННЫЕ И ТОЧНЫЕ НАУКИ::Математика ЭБ БГУ::ТЕХНИЧЕСКИЕ И ПРИКЛАДНЫЕ НАУКИ. ОТРАСЛИ ЭКОНОМИКИ::Автоматика. Вычислительная техника |
Дата публикации: | 2015 |
Издатель: | Elsevier B.V. |
Библиографическое описание источника: | Theor Comput Sci 2015;602:103-113. |
Аннотация: | We are given a sequence of items that can be packed into m unit size bins and the goal is to assign these items online to m bins while minimizing the stretching factor. Bins have infinite capacities and the stretching factor is the size of the largest bin. We present an algorithm with stretching factor 26/17 ≈ 1.5294 improving the best known algorithm by Kellerer and Kotov (2013) [1] with a stretching factor 11/7 ≈ 1.5714. Our algorithm has 2 stages and uses bunch techniques: we aggregate bins into batches sharing a common purpose. © 2015 Elsevier B.V. |
URI документа: | https://elib.bsu.by/handle/123456789/264668 |
DOI документа: | 10.1016/j.tcs.2015.07.065 |
Scopus идентификатор документа: | 84942199470 |
Финансовая поддержка: | This research has been partially supported by project ICS No. 5379 and Belorussian BRFFI grant (Project F13K-078 ). The research of the first and the third author have been partially supported by the LabEx PERSYVAL-Lab ( ANR–11-LABX-0025 ). |
Располагается в коллекциях: | Статьи факультета прикладной математики и информатики |
Полный текст документа:
Файл | Описание | Размер | Формат | |
---|---|---|---|---|
bin_stretching.pdf | 499,25 kB | Adobe PDF | Открыть |
Все документы в Электронной библиотеке защищены авторским правом, все права сохранены.