Dynamic Storage Allocation is the problem of packing given axis-aligned rectangles into a horizontal strip of minimum height by sliding the rectangles vertically but not horizontally. Stated differently, Dynamic Storage Allocation is either the problem of allocating memory space for arriving and departing arrays, or SONET channel assignment.

I will present some new approximation algorithms for Dynamic Storage Allocation and pose an intriguing open question.

This is joint work with Adam Buchsbaum, Claire Kenyon, Nick Reingold, and Mikkel Thorup.