Theory Seminar
Opt vs. Load in Dynamic Storage Allocation
HowardKarloff
WHEN:
Thursday, November 4, 2004 @ 1:30 pm
Add to Google Calendar
Add to Google Calendar
SHARE:
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.