Standard

An Improved Approximation for Packing Big Two-Bar Charts. / Erzin, A. I.; Shenmaier, V. V.

In: Journal of Mathematical Sciences (United States), Vol. 267, No. 4, 11.2022, p. 465-473.

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

Harvard

Erzin, AI & Shenmaier, VV 2022, 'An Improved Approximation for Packing Big Two-Bar Charts', Journal of Mathematical Sciences (United States), vol. 267, no. 4, pp. 465-473. https://doi.org/10.1007/s10958-022-06151-w

APA

Erzin, A. I., & Shenmaier, V. V. (2022). An Improved Approximation for Packing Big Two-Bar Charts. Journal of Mathematical Sciences (United States), 267(4), 465-473. https://doi.org/10.1007/s10958-022-06151-w

Vancouver

Erzin AI, Shenmaier VV. An Improved Approximation for Packing Big Two-Bar Charts. Journal of Mathematical Sciences (United States). 2022 Nov;267(4):465-473. doi: 10.1007/s10958-022-06151-w

Author

Erzin, A. I. ; Shenmaier, V. V. / An Improved Approximation for Packing Big Two-Bar Charts. In: Journal of Mathematical Sciences (United States). 2022 ; Vol. 267, No. 4. pp. 465-473.

BibTeX

@article{ec873a82c4c04d81a86cdc771de7b65c,
title = "An Improved Approximation for Packing Big Two-Bar Charts",
abstract = "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.",
author = "Erzin, {A. I.} and Shenmaier, {V. V.}",
note = "Publisher Copyright: {\textcopyright} 2022, Springer Science+Business Media, LLC, part of Springer Nature.",
year = "2022",
month = nov,
doi = "10.1007/s10958-022-06151-w",
language = "English",
volume = "267",
pages = "465--473",
journal = "Journal of Mathematical Sciences (United States)",
issn = "1072-3374",
publisher = "Springer Nature",
number = "4",

}

RIS

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 -

ID: 39127937