4/3 OPT+2/3 Approximation for Big Two-Bar Charts Packing Problem Научная публикация
| Журнал |
Journal of Mathematical Sciences (United States)
ISSN: 1072-3374 , E-ISSN: 1573-8795 |
||||||
|---|---|---|---|---|---|---|---|
| Вых. Данные | Год: 2023, Том: 269, Номер: 6, Страницы: 813-822 Страниц : 11 DOI: 10.1007/s10958-023-06319-y | ||||||
| Авторы |
|
||||||
| Организации |
|
Информация о финансировании (1)
| 1 | Институт математики им. С.Л. Соболева СО РАН | FWNF-2022-0019 |
Реферат:
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.
Библиографическая ссылка:
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
Даты:
| Принята к публикации: | 11 нояб. 2022 г. |
| Опубликована online: | 7 февр. 2023 г. |
| Опубликована в печати: | 3 мар. 2023 г. |
Идентификаторы БД:
| Scopus: | 2-s2.0-85149262492 |
| РИНЦ: | 60865390 |
| OpenAlex: | W4323045613 |