Approximation Algorithms for Demand Strip Packing
From MaRDI portal
Abstract: In the Demand Strip Packing problem (DSP), we are given a time interval and a collection of tasks, each characterized by a processing time and a demand for a given resource (such as electricity, computational power, etc.). A feasible solution consists of a schedule of the tasks within the mentioned time interval. Our goal is to minimize the peak resource consumption, i.e. the maximum total demand of tasks executed at any point in time. It is known that DSP is NP-hard to approximate below a factor 3/2, and standard techniques for related problems imply a (polynomial-time) 2-approximation. Our main result is a (5/3+eps)-approximation algorithm for any constant eps>0. We also achieve best-possible approximation factors for some relevant special cases.
Recommendations
- Approximation algorithms for multiple strip packing
- Parameterized approximation algorithms for packing problems
- Improved pseudo-polynomial-time approximation for strip packing
- Approximation algorithms for scheduling and packing problems
- A branch and bound algorithm for the strip packing problem
- Hardness of approximation for strip packing
- An exact approach to the strip-packing problem
- Approximate strip packing: revisited
Cited in
(6)- Lower bounds on the performance of online algorithms for relaxed packing problems
- Tight approximation algorithms for geometric bin packing with skewed items
- A branch‐and‐cut algorithm for the irregular strip packing problem with uncertain demands
- Peak demand minimization via sliced strip packing
- Tight approximation algorithms for 2D guillotine strip packing
- Lower bounds on the performance of online algorithms for relaxed packing problems
This page was built for publication: Approximation Algorithms for Demand Strip Packing
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6090894)
