Theory Seminar

Opt vs. Load in Dynamic Storage Allocation


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.

Sponsored by

Martin Stauss