TY - JOUR

T1 - A 4/3 OPT+2/3 Approximation for Big Two-Bar Charts Packing Problem

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

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

AU - Мелиди, Георгий Евстафьевич

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

N1 - The study was carried out within the framework of the state contract of Sobolev Institute of Mathematics (project FWNF-2022-0019).

PY - 2023/2

Y1 - 2023/2

N2 - We consider the two-bar charts packing problem generalizing the strongly NP-hard bin packing problem. We prove that the problem remains strongly NP-hard even if each two-bar chart has at least one bar higher than 1/2. If the first (or second) bar of each two-bar chart is higher than 1/2, we show that the O(n2)-time greedy algorithm with lexicographic ordering of two-bar charts constructs a packing of length at most OPT+1, where OPT is optimum, and present an O(n2.5)-time algorithm that constructs a packing of length at most 4/3 ・ OPT+2/3 in the NP-hard case where each two-bar chart has at least one bar higher than 1/2.

AB - We consider the two-bar charts packing problem generalizing the strongly NP-hard bin packing problem. We prove that the problem remains strongly NP-hard even if each two-bar chart has at least one bar higher than 1/2. If the first (or second) bar of each two-bar chart is higher than 1/2, we show that the O(n2)-time greedy algorithm with lexicographic ordering of two-bar charts constructs a packing of length at most OPT+1, where OPT is optimum, and present an O(n2.5)-time algorithm that constructs a packing of length at most 4/3 ・ OPT+2/3 in the NP-hard case where each two-bar chart has at least one bar higher than 1/2.

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

U2 - 10.1007/s10958-023-06319-y

DO - 10.1007/s10958-023-06319-y

M3 - Article

VL - 269

SP - 813

EP - 822

JO - Journal of Mathematical Sciences (United States)

JF - Journal of Mathematical Sciences (United States)

SN - 1072-3374

IS - 6

ER -