REVIEW
On the 2D Demand Bin Packing Problem: Hardness and Approximation Algorithms
Data Structures and Algorithms · Submitted 18 Aug 2025 · 42 references
Pith's verdict: The abstract advertises a bin packing hardness paper, but the attached full text is an unrelated C*-algebra manuscript; as submitted, none of the advertised results are supported.
T0 · AI review
Why Pith says this
Highlight any text to comment on it.
Referee report
The paper
The paper claims
This paper proves that two simple variants of 2D Demand Bin Packing—short-height tasks and square tasks—cannot be approximated within a factor better than 2 unless P=NP, and provides matching 2-approximations together with a…
The reading
What carries the argument
The framework separates tasks by size: relatively large tasks are packed into bins via a structured solution that yields the matching upper bounds, while relatively small tasks are placed on top using a generalization of First-Fit, the standard greedy algorithm for Bin Packing. The hardness arguments rely on reductions that force an approximate solution to distinguish cases that a factor better than 2 would have to separate.
Extended reading notes
Core claim
The central discovery is that the approximability threshold for the short-height variant and the square variant of 2D Demand Bin Packing is exactly 2: no polynomial-time algorithm can guarantee a factor better than 2 unless P=NP, and the paper's own algorithms achieve factor 2 for these cases. It also claims a 3-approximation for the general variant, using a framework that first computes structured solutions for large tasks and then adds small tasks on top through a generalized First-Fit rule.
Load-bearing premise
The inapproximability results assume P≠NP; if equality held, a polynomial-time algorithm with ratio better than 2 could exist and the claimed lower bounds would fail.
Editorial extensions
If this is right
- If these results are correct, the approximation ratio 2 is the exact threshold for short-height instances and for square instances: no gap remains for future algorithms to exploit.
- The general 3-approximation gives a practical worst-case guarantee for the original scheduling or energy formulation, though tightness of the constant 3 is not claimed.
- The First-Fit generalization transfers a well-understood greedy strategy from one-dimensional bin packing to the two-dimensional demand setting.
Reading between the lines
- A natural next step would be to determine whether the general case also has an inapproximability bound above 2, or whether the 3-approximation can be pushed closer to 2.
- The two hard variants suggest that the difficulty lies in how small heights interact with capacity; bounded-height-ratio instances may admit better ratios.
- The full text supplied with this record is a different manuscript on the 2-adic ring C*-algebra; the summary above reflects the abstract that names the bin-packing results.
Original 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$, 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.
The compiled record
The paper's own sentences, arranged, kept beside the review and separate from it. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.
The abstract, sentence by sentence
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.
background contribution method result interpretation main claim
| # | sentence | role | the authors' own work | states the main conclusion | strength |
|---|---|---|---|---|---|
| s0 | We study a two-dimensional generalization of the classical Bin Packing problem, denoted as 2D Demand Bin Packing. | background 0.54 | 0.80 | 0.03 | asserted 0.91 |
| s1 | 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. | background 0.98 | 0.14 | 0.04 | asserted 0.97 |
| s2 | 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. | result 0.73 | 0.97 | 0.81 | asserted 1.00 |
| s3 | 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. | method 0.99 | 0.92 | 0.08 | asserted 1.00 |
What was examined, and what was not
- arXiv listing abstract v1
- full text
- figures and tables
- references and citing sentences
- relations to other papers
- P abstract
- S sections
- T body sentences
- C citations
- R cross-paper relations
References
Discussion
Disagree with the review, or know something it missed? Leave a comment, highlight any passage above to comment on it, or challenge this review formally.