|
ИСТИНА |
Войти в систему Регистрация |
ИСТИНА ПсковГУ |
||
An O(n log n)-time OPT+1 approximation for packing big 2-bar chartsтезисы доклада
- Авторы: Erzin A.I., Kononov A.V., Nazarenko S.A., Sharankhaev K.
- Сборник: Mathematical Optimization Theory and Operations Research: Recent Trends
- Серия: Communications in Computer and Information Science
- Том: 1881
- Тезисы
- Год издания: 2023
- Издательство: Springer-Verlag GmbH
- Местоположение издательства: Heidelberg, Germany
- Первая страница: 122
- Последняя страница: 133
- DOI: 10.1007/978-3-031-43257-6_10
- Аннотация: Given a sequence of bins and n bar charts consisting of two bars each (2-BCs). Every bar has a positive height not exceeding 1. Each bin can contain any subset of bars of total height at most 1. It is required to pack all 2-BCs into the minimal number of bins so that the bars of each 2-BC do not change their order and occupy adjacent bins. Previously, a special case of the problem was considered where the first bars of any two 2-BCs cannot be placed into the same bin. For this case an O(n^2)-time algorithm that constructs a packing of length at most OPT+1, where OPT is the optimum, was presented. In this paper, we propose a new, less time-consuming algorithm that also constructs a packing of length at most OPT+1 for the same case of the problem with time complexity equals to O(nlog n).
- Добавил в систему: Кононов Александр Вениаминович