On the 2D Demand Bin Packing Problem: Hardness and Approximation Algorithms
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866911110486032384 |
|---|---|
| author | Albers, Susanne Gálvez, Waldo Özdemir, Ömer Behic |
| author_facet | Albers, Susanne Gálvez, Waldo Özdemir, Ömer Behic |
| contents | We study a two-dimensional generalization of the classical Bin Packing problem, denoted as 2D Demand Bin Packing. In this context, each bin is a horizontal timeline, and rectangular tasks (representing electric appliances or computational requirements) must be allocated into the minimum number of bins so that the sum of the heights of tasks at any point in time is at most a given constant capacity. We prove that simple variants of the problem are NP-hard to approximate within a factor better than $2$, namely when tasks have short height and when they are squares, and provide best-possible approximation algorithms for them; we also present a simple $3$-approximation for the general case. All our algorithms are based on a general framework that computes structured solutions for relatively large tasks, while including relatively small tasks on top via a generalization of the well-known First-Fit algorithm for Bin Packing. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_13347 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On the 2D Demand Bin Packing Problem: Hardness and Approximation Algorithms Albers, Susanne Gálvez, Waldo Özdemir, Ömer Behic Data Structures and Algorithms We study a two-dimensional generalization of the classical Bin Packing problem, denoted as 2D Demand Bin Packing. In this context, each bin is a horizontal timeline, and rectangular tasks (representing electric appliances or computational requirements) must be allocated into the minimum number of bins so that the sum of the heights of tasks at any point in time is at most a given constant capacity. We prove that simple variants of the problem are NP-hard to approximate within a factor better than $2$, namely when tasks have short height and when they are squares, and provide best-possible approximation algorithms for them; we also present a simple $3$-approximation for the general case. All our algorithms are based on a general framework that computes structured solutions for relatively large tasks, while including relatively small tasks on top via a generalization of the well-known First-Fit algorithm for Bin Packing. |
| title | On the 2D Demand Bin Packing Problem: Hardness and Approximation Algorithms |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2508.13347 |