Competitive Video on Demand Schedulers for Popular Movies

TitleCompetitive Video on Demand Schedulers for Popular Movies
Publication TypeJournal Article
Year of Publication2003
AuthorsBouras, C, Kapoulas, V, Spirakis, P, Pantziou, G
JournalDiscrete Applied Mathematics, Special Issue Algorithmic Aspects of Communication, Elsevier Science, Vol. 129, Issue 1
PaginationPP. 49 - 61

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 “adaptive” randomized scheduler which initially is not aware of the movie popularities but it adapts to it, and achieves the same asymptotic competitive ratio.