Paper by Erik D. Demaine

Therese Biedl, Erik D. Demaine, Alexander Golynski, Joseph D. Horton, Alejandro López-Ortiz, Guillaume Poirier, and Claude-Guy Quimper, “Optimal Dynamic Video-On-Demand using Adaptive Broadcasting”, in Proceedings of the 11th Annual European Symposium on Algorithms (ESA 2003), Lecture Notes in Computer Science, volume 2832, Budapest, Hungary, September 15–20, 2003, pages 90–101.

We consider the transmission of a movie over a broadcast network to support several viewers who start watching at arbitrary times, after a wait of at most twait minutes. A recent approach called harmonic broadcasting optimally solves the case of many viewers watching a movie using a constant amount of bandwidth. We consider the more general setting in which a movie is watched by an arbitrary number v of viewers, and v changes dynamically. A natural objective is to minimize the amount of resources required to achieve this task. We introduce two natural measures of resource consumption and performance—total bandwidth usage and maximum momentary bandwidth usage—and propose strategies which are optimal for each of them. In particular, we show that an adaptive form of pyramid broadcasting is optimal for both measures simultaneously, up to constant factors. We also show that the maximum throughput for a fixed network bandwidth cannot be obtained by any online strategy.

This paper is also available from SpringerLink.

The paper is available in PostScript (363k), gzipped PostScript (157k), and PDF (160k).
See information on file formats.
[Google Scholar search]

See also other papers by Erik Demaine.
These pages are generated automagically from a BibTeX file.
Last updated May 16, 2024 by Erik Demaine.