Next: Compression and Representation
Up: Data Storage
Previous: MAXIMUM D-VECTOR COVERING
  Index
- 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 [192].
- Comment:
Approximable within 5/2 if the sizes are powers of 2 and within 2
if only two sizes are allowed [192].
Viggo Kann
2000-03-20