Opt vs. Load in Dynamic Storage Allocation

AT&T LABS–RESEARCH
The SONET Channel Assignment Problem in telecommunications
or Dynamic Storage Allocation Problem in memory management
is the geometric problem of packing given axis-aligned rectangles
into a horizontal strip of minimum height by sliding the
rectangles vertically but not horizontally.
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.