Next: Compression and Representation Up: Data Storage Previous: MAXIMUM D-VECTOR COVERING Index

### MINIMUM DYNAMIC STORAGE ALLOCATION

- INSTANCE: Set A of items to be stored, each having a size , an arrival time , and a departure time .

- SOLUTION: A feasible allocation of storage for A, i.e., a function such that, for all , if is nonempty then either or .

- MEASURE: The size of the allocation, i.e., .

- Good News: Approximable within 5 [180].

- Comment: Approximable within 5/2 if the sizes are powers of 2 and within 2 if only two sizes are allowed [180].