TY - GEN

T1 - An O(nlogn)-Time Algorithm for Linearly Ordered Packing of 2-Bar Charts into OPT+1 Bins

AU - Ерзин, Адиль Ильясович

AU - Кононов, Александр Вениаминович

AU - Назаренко, Степан Андреевич

AU - Шаранхаев, Константин Иванович

N1 - Conference code: 22

PY - 2023

Y1 - 2023

N2 - 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(nlogn).

AB - 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(nlogn).

KW - Approximation

KW - Bar charts

KW - Packing

UR - https://www.scopus.com/record/display.uri?eid=2-s2.0-85174573258&origin=inward&txGid=498c35c2aec3baefae9c6c8ffcfd95e0

U2 - 10.1007/978-3-031-43257-6_10

DO - 10.1007/978-3-031-43257-6_10

M3 - Conference contribution

SN - 9783031353048

T3 - Communications in Computer and Information Science

SP - 122

EP - 133

BT - Mathematical Optimization Theory and Operations Research - 22nd International Conference, MOTOR 2023, Proceedings

A2 - Goos, Gerhard

A2 - Hartmanis, Juris

PB - Springer Science and Business Media Deutschland GmbH

T2 - 22nd International Conference on Mathematical Optimization Theory and Operations Research

Y2 - 2 July 2023 through 8 July 2023

ER -