For the classic dynamic storage/spectrum allocation
problem, we show that knowledge of the durations of the requests
is of no great use to an online algorithm in the worst case.
This answers an open question posed by
Naor, Orda, and Petruschka.
More precisely, we show that the competitive ratio of every
randomized algorithm against an oblivious adversary is
$\Omega(\frac{\log x }{\log \log x})$, where $x$ may be any
of several different parameters used in the literature.
It is known that First Fit, which does not require knowledge
of the durations of the task,
is logarithmically competitive in these parameters.
