Offline green bin packing and its constrained variant
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866908840449015808 |
|---|---|
| author | Gong, Mingyang Mumey, Brendan |
| author_facet | Gong, Mingyang Mumey, Brendan |
| contents | In this paper, we study the {\em green bin packing} (GBP) problem where $β\ge 0$ and $G \in [0, 1]$ are two given values as part of the input. The energy consumed by a bin is $\max \{0, β(x-G) \}$ where $x$ is the total size of the items packed into the bin. The GBP aims to pack all items into a set of unit-capacity bins so that the number of bins used plus the total energy consumption is minimized. When $β= 0$ or $G = 1$, GBP is reduced to the classic bin packing (BP) problem. In the {\em constrained green bin packing} (CGBP) problem, the objective is to minimize the number of bins used to pack all items while the total energy consumption does not exceed a given upper bound $U$. We present an APTAS and a $\frac 32$-approximation algorithm for both GBP and CGBP, where the ratio $\frac 32$ matches the lower bound of BP. Keywords: Green bin packing; constrained green bin packing; approximation scheme; offline algorithms |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_16867 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Offline green bin packing and its constrained variant Gong, Mingyang Mumey, Brendan Data Structures and Algorithms F.2.2 In this paper, we study the {\em green bin packing} (GBP) problem where $β\ge 0$ and $G \in [0, 1]$ are two given values as part of the input. The energy consumed by a bin is $\max \{0, β(x-G) \}$ where $x$ is the total size of the items packed into the bin. The GBP aims to pack all items into a set of unit-capacity bins so that the number of bins used plus the total energy consumption is minimized. When $β= 0$ or $G = 1$, GBP is reduced to the classic bin packing (BP) problem. In the {\em constrained green bin packing} (CGBP) problem, the objective is to minimize the number of bins used to pack all items while the total energy consumption does not exceed a given upper bound $U$. We present an APTAS and a $\frac 32$-approximation algorithm for both GBP and CGBP, where the ratio $\frac 32$ matches the lower bound of BP. Keywords: Green bin packing; constrained green bin packing; approximation scheme; offline algorithms |
| title | Offline green bin packing and its constrained variant |
| topic | Data Structures and Algorithms F.2.2 |
| url | https://arxiv.org/abs/2602.16867 |