Dynamic spectrum allocation: the impotency of duration notification
Bala Kalyanasundaram, Kirk R. Pruhs · Journal of Scheduling · 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 on-line algorithm in the worst case. This answers an open question posed by Naor et al. [9]. More precisely, we show that the competitive ratio of every randomized algorithm against an oblivious adversary is Ω(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. Copyright © 2000 John Wiley & Sons, Ltd.