Dynamic Spectrum Allocation: The Impotency of Duration Notification

Bala Kalyanasundaram and Kirk Pruhs

To appear at Foundations of Software Technology and Theoretical Computer Science (FSTTCS2000), New Delhi, India, December 13-15 2000


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.

Server START Conference Manager
Update Time 14 Aug 2000 at 17:41:23
Maintainer fsttcs20@cse.iitd.ernet.in.
Start Conference Manager
Conference Systems