𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On-line stream merging in a general setting

✍ Scribed by Wun-Tat Chan; Tak-Wah Lam; Hing-Fung Ting; Prudence W.H. Wong

Publisher
Elsevier Science
Year
2003
Tongue
English
Weight
650 KB
Volume
296
Category
Article
ISSN
0304-3975

No coin nor oath required. For personal study only.

✦ Synopsis

This paper is concerned with on-line scheduling algorithms for merging streams in a video-ondemand system so as to minimize the server bandwidth. We present the ΓΏrst algorithm that has a constant competitive factor (precisely, 5). Our algorithm, unlike previous ones, is not limited to the scenario where clients are equipped with large bu er and client receiving bandwidth. It remains 5-competitive in all settings of bu er size and receiving bandwidth. Technically speaking, our algorithm is based on a novel observation that the behavior of any schedule can be modeled by a rectilinear (binary) tree on a grid. This observation eases the analysis of our algorithm as well as the optimal algorithm.

πŸ“œ SIMILAR VOLUMES

Difference equations in a general settin
Difference equations in a general setting
✍ D.J. Hartfiel πŸ“‚ Article πŸ“… 2000 πŸ› Elsevier Science 🌐 English βš– 99 KB

For a square matrix A, the difference equation y k+1 = y k A generates a sequence of vectors y 0 , y 1 , . . . The long run behavior of this sequence is described in terms of a group obtained from A, A 2 . . . The results are given in a topological semigroup setting so they can also be applied to mo