Name
Abstract | ||
|---|---|---|
One advantage of smart grids is that they can reduce the peak load by distributing electricity-demands over multiple short intervals. Finding a schedule that minimizes the peak load corresponds to a variant of a strip packing problem. Normally, for strip packing problems, a given set of axis-aligned rectangles must be packed into a fixed-width strip, and the goal is to minimize the height of the strip. The electricity-allocation application can be modelled as strip packing with slicing: each rectangle may be cut vertically into multiple slices and the slices may be packed into the strip as individual pieces. The stacking constraint forbids solutions in which a vertical line intersects two slices of the same rectangle. We give a fully polynomial time approximation scheme for this problem, as well as a practical polynomial time algorithm that slices each rectangle at most once and yields a solution of height at most 5/3 times the optimal height. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1007/978-3-642-40104-6_3 | WADS |
Keywords | Field | DocType |
strip packing,strip packing problem,polynomial time approximation scheme,fixed-width strip,peak load corresponds,peak load,multiple slice,optimal height,axis-aligned rectangle,multiple short interval,smart-grid electricity allocation | Combinatorics,Packing problems,Smart grid,Electricity,Slicing,Rectangle,Time complexity,Polynomial-time approximation scheme,Mathematics,Stacking | Conference |
Citations | PageRank | References |
7 | 0.62 | 16 |
Authors | ||
8 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Soroush Alamdari | 1 | 56 | 5.93 |
| Therese Biedl | 2 | 902 | 106.36 |
| Timothy M. Chan | 3 | 2033 | 150.55 |
| Elyot Grant | 4 | 86 | 7.59 |
| Krishnam Raju Jampani | 5 | 37 | 3.15 |
| Srinivasan Keshav | 6 | 3778 | 761.32 |
| Anna Lubiw | 7 | 753 | 95.36 |
| Vinayak Pathak | 8 | 50 | 4.24 |