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
Last updated November 16, 2017 by