Abstract: 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(n2)-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(n log n).

Cite: Erzin A. , Kononov A. , Nazarenko S. , Sharankhaev K.
An O(n\log n)-Time Algorithm for Linearly Ordered Packing of 2-Bar Charts into OPT+1 Bins
In compilation Mathematical Optimization Theory and Operations Research: Recent Trends. – Springer., 2023. – Т.1881. – C.122-133. DOI: 10.1007/978-3-031-43257-6_10 Scopus OpenAlex

Dates:

Published print:	Sep 21, 2023
Published online:	Sep 21, 2023

Identifiers:

Scopus:	2-s2.0-85174573258
OpenAlex:	W4386891738

Citing: Пока нет цитирований

Altmetrics: