# Hardness and Tight Approximations of Demand Strip Packing

arXiv: https://arxiv.org/abs/2404.15917 · HTML: https://mlsanity.com/paper/2404.15917/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 Apr 2024.

## Built on by (most cited first, 1 of 1)

- [Introducing Resizable Region Packing Problem in Image Generation, with a Heuristic Solution](https://mlsanity.com/paper/2509.16363/) (2025)

## Abstract (arXiv)

We settle the pseudo-polynomial complexity of the Demand Strip Packing (DSP) problem: Given a strip of fixed width and a set of items with widths and heights, the items must be placed inside the strip with the objective of minimizing the peak height. This problem has gained significant scientific interest due to its relevance in smart grids[Deppert et al. APPROX'21, G'alvez et al. APPROX'21]. Smart Grids are a modern form of electrical grid that provide opportunities for optimization. They are forecast to impact the future of energy provision significantly. Algorithms running in pseudo-polynomial time lend themselves to these applications as considered time intervals, such as days, are small. Moreover, such algorithms can provide superior approximation guarantees over those running in polynomial time. Consequently, they evoke scientific interest in related problems. We prove that Demand Strip Packing is strongly NP-hard for approximation ratios below 5/4. Through this proof, we provide novel insights into the relation of packing and scheduling problems. Using these insights, we show a series of frameworks that solve both Demand Strip Packing and Parallel Task Scheduling optimally when increasing the strip's width or number of machines. Such alterations to problems are known as resource augmentation. Applications are found when penalty costs are prohibitively large. Finally, we provide a pseudo-polynomial time approximation algorithm for DSP with an approximation ratio of (5/4+varepsilon), which is nearly optimal assuming Pneq NP. The construction of this algorithm provides several insights into the structure of DSP solutions and uses novel techniques to restructure optimal solutions.