On the 2D Demand Bin Packing Problem: Hardness and Approximation Algorithms
Susanne Albers, Waldo Gálvez, Ömer Behic Özdemir · 2025
Read On the 2D Demand Bin Packing Problem: Hardness and Approximation Algorithms by Susanne Albers, Waldo Gálvez, Ömer Behic Özdemir (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-13347.txt.
Introduction
Susanne Albers, Waldo Gálvez, and Ömer Behic Özdemir study a two-dimensional twist on the classic bin packing problem, in a 2025 paper. In their version, each bin is a timeline, and each job is a rectangle with a set length and height. Think of appliances drawing power over time. Jobs must fit into as few timelines as possible without the stacked heights ever passing a fixed cap.
The authors prove that even simple versions are hard: no fast method can promise answers within a factor of two of the best, for short jobs or for square jobs alike. For those versions they give methods that reach the best promise allowed. For the general problem they offer a method within a factor of three. All the methods sort big jobs into a tidy frame first, then slot small jobs on top with a classic packing rule.
Catalog record
| CREATOR | Susanne Albers, Waldo Gálvez, Ömer Behic Özdemir |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 78 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2508-13347
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
On the 2D Demand Bin Packing Problem: Hardness and Approximation Algorithms Susanne Albers, Waldo Gálvez, Ömer Behic Özdemir Abstract 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 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 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. 1 Introduction In this article, we consider a two-dimensional generalization of the classical Bin Packing problem, denoted as 2D Demand Bin Packing . An instance of the problem is defined by bins, where each bin corresponds to an axis-parallel rectangular region in the plane of height C and width T , and a set of n tasks, where each task i is a rectangle characterized by its height h_{i} and width w_{i} . The goal is to partition the given tasks into the minimum number of groups such that each group can be feasibly allocated into a bin; in this context, an allocation of a subset I of tasks is a function that specifies, for each task i , the coordinate in the X -axis where the task starts (i.e., if task i starts at t\leq T-w_{i} , it is placed in the interval (t,t+w_{i}) ). An allocation into a bin is feasible if, for each t\in[0,T] , the total height of tasks intersecting t is at most C . See Figure 1 for an example. A closely related problem is the well-studied 2D Geometric Bin Packing problem [ 13 , 3 ] , where the input is the same as before but the tasks are required to be embedded as non-overlapping axis-parallel rectangles into the bins 1 1 1 2D Demand Bin Packing can be thought as a version of 2D Geometric Bin Packing where each rectangle i is replaced by w_{i} rectangles of height h_{i} and width 1 , but these slices must be placed into consecutive horizontal positions in the same bin . The 2D Geometric Bin Packing problem models scenarios where tasks require contiguous and fixed portions of a given resource, such as allocating consecutive frequency or memory locations to given requirements, or cutting pieces out of sheets of some raw material (such as leather, wood, metal, etc.). However, Demand Allocation problems such as 2D Demand Bin Packing have received increasing attention because they better capture scenarios where geometric constraints are not required. For example, in the context of Energy Management, we might think of tasks as electric appliances, whose height corresponds to the amount of energy they consume, and their width corresponds to the amount of time they are required; hence, 2D Demand Bin Packing would correspond to deciding how many periods of T units of time are required to execute all the tasks without overloading the system capacity C (see [ 20 , 1 ] for other examples of similar scenarios in the context of Smart-Grid Scheduling). It is worth remarking that geometric constraints do not play a role here as we only care about the accumulated energy consumption at each point in time; furthermore, enforcing such constraints might lead to inefficient solutions (see for instance Figure 1 ), suggesting that techniques specifically designed for the Demand Allocation context are required. It is not difficult to verify that it is NP-hard to decide if a set of given tasks can be allocated into one bin or not (for example via a reduction from the Partition problem, encoding the Partition instance into the widths of the tasks and the heights being half the height of the bin). This already implies that, for any \varepsilon>0 , there is no (2-\varepsilon) -approximation for 2D Demand Bin Packing (and also for 2D Geometric Bin Packing). It is known that 2D Geometric Bin Packing admits a 2 -approximation which is best possible unless P=NP [ 13 ] ; however, to the best of our knowledge, 2D Demand Bin Packing has not been explicitly studied before. 1 2 3 4 1 2 3 4 h_{i_{1}} w_{i_{1}} i_{1} i_{2} i_{3} i_{4} i_{5} i_{6} i_{7} C i_{1} i_{5} i_{3} i_{3} i_{6} i_{7} i_{4} i_{4} i_{2} i_{2} i_{1} i_{2} i_{4} i_{3} i_{8} i_{9} i_{10} i_{11} i_{12} i_{13} i_{14} i_{5} i_{6} i_{7} i_{7} Figure 1 : (Left) : Example of an instance of 2D Demand Bin Packing, with parameters T=4 and C=3 , and a feasible solution defined by two bins. (Right) : Example of an instance of 2D Demand Bin Packing of squares into a square bin that fits into one bin, but that does not allow a geometric packing of the squares into the bin (see Appendix B ). 1.1 Our Results We provide best-possible approximation algorithms for two relevant special cases of 2D Demand Bin Packing that preserve the aforementioned hardness of approximation (see Appendix A ): When tasks have height at most \frac{1}{9}C , denoted as 2D Demand Bin Packing for short tasks , and when tasks have equal height and width, denoted as 2D Demand Bin Packing for square tasks . We also provide a simple 3 -approximation for the general case. Our results are based on a common framework that consists of two steps: We classify the tasks according to their heights and widths into large and small (the precise definition will depend on the context). Our main technical contribution states that, as long as large tasks can be allocated into bins so that each bin either has enough total area or has a special structure (namely that the sequence of total loads for each point in time is monotonically non-increasing), and a certain relation between the parameters defining large and small tasks is satisfied, then small tasks can be placed on top of the solution without adding extra bins (see Lemma 1 ). The algorithm to place small tasks is an adaptation to the two-dimensional case of the classical First-Fit algorithm for Bin Packing, specially tailored for the 2D Demand Allocation context. The previous framework allows to focus solely on how to place large tasks with the required structure, which in most cases can be achieved by means of classical Bin Packing or 2D Geometric Bin Packing routines. Our results show that the 2D Demand Allocation context indeed allows for simpler algorithms in comparison to its geometric counterparts [ 21 , 13 ] . 1.2 Related Results The (one-dimensional) Bin Packing problem is one of the most classical and well-studied problems in Combinatorial Optimization. It is known to be strongly NP-hard and, for any \varepsilon>0 , there cannot be a \left(\frac{3}{2}-\varepsilon\right) -approximation unless P=NP [ 11 ] ;