Standard

A 4/3 OPT+2/3 Approximation for Big Two-Bar Charts Packing Problem. / Ерзин, Адиль Ильясович; Кононов, Александр Вениаминович; Мелиди, Георгий Евстафьевич и др.

в: Journal of Mathematical Sciences (United States), Том 269, № 6, 02.2023, стр. 813–822.

Результаты исследований: Научные публикации в периодических изданияхстатьяРецензирование

Harvard

Ерзин, АИ, Кононов, АВ, Мелиди, ГЕ & Назаренко, СА 2023, 'A 4/3 OPT+2/3 Approximation for Big Two-Bar Charts Packing Problem', Journal of Mathematical Sciences (United States), Том. 269, № 6, стр. 813–822. https://doi.org/10.1007/s10958-023-06319-y

APA

Vancouver

Ерзин АИ, Кононов АВ, Мелиди ГЕ, Назаренко СА. A 4/3 OPT+2/3 Approximation for Big Two-Bar Charts Packing Problem. Journal of Mathematical Sciences (United States). 2023 февр.;269(6):813–822. doi: 10.1007/s10958-023-06319-y

Author

Ерзин, Адиль Ильясович ; Кононов, Александр Вениаминович ; Мелиди, Георгий Евстафьевич и др. / A 4/3 OPT+2/3 Approximation for Big Two-Bar Charts Packing Problem. в: Journal of Mathematical Sciences (United States). 2023 ; Том 269, № 6. стр. 813–822.

BibTeX

@article{f03f25e412b748c5946ac1fc9b454b47,
title = "A 4/3 OPT+2/3 Approximation for Big Two-Bar Charts Packing Problem",
abstract = "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.",
author = "Ерзин, {Адиль Ильясович} and Кононов, {Александр Вениаминович} and Мелиди, {Георгий Евстафьевич} and Назаренко, {Степан Андреевич}",
note = "The study was carried out within the framework of the state contract of Sobolev Institute of Mathematics (project FWNF-2022-0019).",
year = "2023",
month = feb,
doi = "10.1007/s10958-023-06319-y",
language = "English",
volume = "269",
pages = "813–822",
journal = "Journal of Mathematical Sciences (United States)",
issn = "1072-3374",
publisher = "Springer Nature",
number = "6",

}

RIS

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 -

ID: 55570518