4/3 OPT+2/3 Approximation for Big Two-Bar Charts Packing Problem Full article
| Journal |
Journal of Mathematical Sciences (United States)
ISSN: 1072-3374 , E-ISSN: 1573-8795 |
||||||
|---|---|---|---|---|---|---|---|
| Output data | Year: 2023, Volume: 269, Number: 6, Pages: 813-822 Pages count : 11 DOI: 10.1007/s10958-023-06319-y | ||||||
| Authors |
|
||||||
| Affiliations |
|
Funding (1)
| 1 | Sobolev Institute of Mathematics | FWNF-2022-0019 |
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.
Cite:
Erzin A.I.
, Kononov A.V.
, Melidi G.E.
, Nazarenko S.A.
4/3 OPT+2/3 Approximation for Big Two-Bar Charts Packing Problem
Journal of Mathematical Sciences (United States). 2023. V.269. N6. P.813-822. DOI: 10.1007/s10958-023-06319-y Scopus РИНЦ OpenAlex
4/3 OPT+2/3 Approximation for Big Two-Bar Charts Packing Problem
Journal of Mathematical Sciences (United States). 2023. V.269. N6. P.813-822. DOI: 10.1007/s10958-023-06319-y Scopus РИНЦ OpenAlex
Dates:
| Accepted: | Nov 11, 2022 |
| Published online: | Feb 7, 2023 |
| Published print: | Mar 3, 2023 |
Identifiers:
| Scopus: | 2-s2.0-85149262492 |
| Elibrary: | 60865390 |
| OpenAlex: | W4323045613 |