@article {3048, title = {Competitive Video on Demand Schedulers for Popular Movies}, journal = {Discrete Applied Mathematics, Special Issue Algorithmic Aspects of Communication, Elsevier Science, Vol. 129, Issue 1}, year = {2003}, pages = {PP. 49 - 61}, abstract = {

In this paper we investigate the online video on demand problem, namely having to accept or reject a request for a movie without knowing the future requests. We present online movie-scheduling schemes that implement the principles of refusal by choice and delayed noti- 4cation. A novel way to schedule movies that exploits the knowledge of the distribution of the preference of requests for movies, is shown to have a competitive ratio that outperforms all the previously knownschemes inpractical situations. Infact, our scheduler has a competitive ratio bounded above by a constant, independent of the number of the users, channels, or movies, in the case that a large fraction of the requests tends to concentrate in a small number of movies. We extend our approach by presenting an {\textquotedblleft}adaptive{\textquotedblright} randomized scheduler which initially is not aware of the movie popularities but it adapts to it, and achieves the same asymptotic competitive ratio.

}, author = {Christos Bouras and Vaggelis Kapoulas and Paul Spirakis and G Pantziou} } @conference {2847, title = {Competitive Video on Demand Schedulers for Popular Movies}, booktitle = {Workshop on Algorithmic Aspects of Communications (ICALP satellite workshop), Bologna, Italy}, year = {1997}, month = {11 - 12 July}, abstract = {

In this paper we investigate the online video on demand problem, namely having to accept or reject a request for a movie without knowing the future requests. We present online movie-scheduling schemes that implement the principles of refusal by choice and delayed noti cation. A novel way to schedule movies that exploits the knowledge of the distribution of the preference of requests for movies, is shown to have a competitive ratio that outperforms all the previously known schemes in practical situations. In fact, our scheduler has a competitive ratio bounded above by a constant, independent of the number of the users, channels, or movies, in the case that a large fraction of the requests tends to concentrate in a small number of movies. We extend our approach by presenting an \adaptive" randomized scheduler which initially is not aware of the movie popularities but it adapts to it, and achieves a similar asymptotic competitive ratio.

}, author = {Christos Bouras and Vaggelis Kapoulas and Paul Spirakis and G Pantziou} } @conference {2849, title = {Randomized adaptive video on demand}, booktitle = {15th ACM-PODC, Philadelphia PA, USA}, year = {1996}, pages = {179}, author = {Christos Bouras and Vaggelis Kapoulas and Paul Spirakis and G Pantziou} }