TY - JOUR

T1 - An Improved Approximation for Packing Big Two-Bar Charts

AU - Erzin, A. I.

AU - Shenmaier, V. V.

N1 - Publisher Copyright: © 2022, Springer Science+Business Media, LLC, part of Springer Nature.

PY - 2022/11

Y1 - 2022/11

N2 - We consider the two-bar charts packing problem which is a generalization of the strongly NP-hard bin packing problem and 2-D vector packing problem. We propose an O(n2.5)-time 16/11-approximation algorithm for packing two-bar charts when at least one bar of each two-bar chart has height more than 1/2 and an O(n2.5)-time 5/4-approximation algorithm for packing nonincreasing or nondecreasing two-bar charts when each two-bar chart has at least one bar higher than 1/2.

AB - We consider the two-bar charts packing problem which is a generalization of the strongly NP-hard bin packing problem and 2-D vector packing problem. We propose an O(n2.5)-time 16/11-approximation algorithm for packing two-bar charts when at least one bar of each two-bar chart has height more than 1/2 and an O(n2.5)-time 5/4-approximation algorithm for packing nonincreasing or nondecreasing two-bar charts when each two-bar chart has at least one bar higher than 1/2.

UR - http://www.scopus.com/inward/record.url?scp=85141119462&partnerID=8YFLogxK

UR - https://www.mendeley.com/catalogue/72287ffd-ae89-3394-9cb2-3fac60eb1e71/

U2 - 10.1007/s10958-022-06151-w

DO - 10.1007/s10958-022-06151-w

M3 - Article

AN - SCOPUS:85141119462

VL - 267

SP - 465

EP - 473

JO - Journal of Mathematical Sciences (United States)

JF - Journal of Mathematical Sciences (United States)

SN - 1072-3374

IS - 4

ER -