Standard

Updated Estimates for Algorithms for Packing 2-Bar Charts in a Strip. / Nazarenko, S. A.

In: Journal of Applied and Industrial Mathematics, Vol. 18, No. 4, 11, 12.2024, p. 759-774.

Research output: Contribution to journal › Article › peer-review

Harvard

Nazarenko, SA 2024, 'Updated Estimates for Algorithms for Packing 2-Bar Charts in a Strip', Journal of Applied and Industrial Mathematics, vol. 18, no. 4, 11, pp. 759-774. https://doi.org/10.1134/S1990478924040112

APA

Nazarenko, S. A. (2024). Updated Estimates for Algorithms for Packing 2-Bar Charts in a Strip. Journal of Applied and Industrial Mathematics, 18(4), 759-774. [11]. https://doi.org/10.1134/S1990478924040112

Vancouver

Nazarenko SA. Updated Estimates for Algorithms for Packing 2-Bar Charts in a Strip. Journal of Applied and Industrial Mathematics. 2024 Dec;18(4):759-774. 11. doi: 10.1134/S1990478924040112

Author

Nazarenko, S. A. / Updated Estimates for Algorithms for Packing 2-Bar Charts in a Strip. In: Journal of Applied and Industrial Mathematics. 2024 ; Vol. 18, No. 4. pp. 759-774.

BibTeX

@article{7aaaa63277d5410b9cb7702a04602d10,
title = "Updated Estimates for Algorithms for Packing 2-Bar Charts in a Strip",
abstract = "We consider a two-bar charts packing problem in which it is necessary to pack bar chartsconsisting of two bars in a unit-height strip of minimum length. Each bar has a height of at most1 and unit length. The problem under consideration is NP-hard and generalizes the bin packingproblem and two-dimensional vector packing problem. This paper proves updated accuracyestimates and time complexity for several previously developed polynomial approximationalgorithms for the two-bar charts packing problem and particular cases of the problem. We showthe attainability of the estimates. Furthermore, we consider a problem of packing an unlimitednumber of bar charts belonging to different types and propose a polynomial algorithm to solve the problem incase.",
keywords = "NP-hard problem, a priori estimate, attainability, bar chart, strip packing",
author = "Nazarenko, {S. A.}",
note = "Назаренко С.А. Уточнённые оценки для алгоритмов упаковки 2-гистограмм в полосу // Дискретный анализ и исследование операций. – 2024. – Т. 31. - № 4 (162). – С. 90-115. Исследование выполнено за счёт бюджета Новосибирского государственного университета.",
year = "2024",
month = dec,
doi = "10.1134/S1990478924040112",
language = "English",
volume = "18",
pages = "759--774",
journal = "Journal of Applied and Industrial Mathematics",
issn = "1990-4789",
publisher = "Maik Nauka-Interperiodica Publishing",
number = "4",

}

RIS

TY - JOUR

T1 - Updated Estimates for Algorithms for Packing 2-Bar Charts in a Strip

AU - Nazarenko, S. A.

N1 - Назаренко С.А. Уточнённые оценки для алгоритмов упаковки 2-гистограмм в полосу // Дискретный анализ и исследование операций. – 2024. – Т. 31. - № 4 (162). – С. 90-115. Исследование выполнено за счёт бюджета Новосибирского государственного университета.

PY - 2024/12

Y1 - 2024/12

N2 - We consider a two-bar charts packing problem in which it is necessary to pack bar chartsconsisting of two bars in a unit-height strip of minimum length. Each bar has a height of at most1 and unit length. The problem under consideration is NP-hard and generalizes the bin packingproblem and two-dimensional vector packing problem. This paper proves updated accuracyestimates and time complexity for several previously developed polynomial approximationalgorithms for the two-bar charts packing problem and particular cases of the problem. We showthe attainability of the estimates. Furthermore, we consider a problem of packing an unlimitednumber of bar charts belonging to different types and propose a polynomial algorithm to solve the problem incase.

AB - We consider a two-bar charts packing problem in which it is necessary to pack bar chartsconsisting of two bars in a unit-height strip of minimum length. Each bar has a height of at most1 and unit length. The problem under consideration is NP-hard and generalizes the bin packingproblem and two-dimensional vector packing problem. This paper proves updated accuracyestimates and time complexity for several previously developed polynomial approximationalgorithms for the two-bar charts packing problem and particular cases of the problem. We showthe attainability of the estimates. Furthermore, we consider a problem of packing an unlimitednumber of bar charts belonging to different types and propose a polynomial algorithm to solve the problem incase.

KW - NP-hard problem

KW - a priori estimate

KW - attainability

KW - bar chart

KW - strip packing

UR - https://www.scopus.com/pages/publications/105010496598

UR - https://www.elibrary.ru/item.asp?id=82621660

UR - https://www.elibrary.ru/item.asp?id=82606995

UR - https://www.mendeley.com/catalogue/dbc9c63b-12a8-3873-bb97-ab07a00ebc36/

U2 - 10.1134/S1990478924040112

DO - 10.1134/S1990478924040112

M3 - Article

VL - 18

SP - 759

EP - 774

JO - Journal of Applied and Industrial Mathematics

JF - Journal of Applied and Industrial Mathematics

SN - 1990-4789

IS - 4

M1 - 11

ER -

ID: 68667616