A 5-competitive on-line scheduler for merging video streams
Wun-Tat Chan, Tak‐Wah Lam, Hing‐Fung Ting, Wai-Ha Wong · 2005
This paper is concerned with an on-line scheduling problem arising from video-on-demand (VOD) systems that support stream merging. Most previous work on this problem focuses on empirical results; Bar-Noy and Ladner [3] are the first to consider worst-case performance and give an on-line algorithm with competitive ratio bounded by ,w here , is the number of requests, and is the guaranteed startup delay measured as a fraction of the time for a full stream. In this paper we give a new on-line algorithm that improves the competitive ratio to a constant (precisely, 5). Our result implies that the performance does not deteriorate in dealing with a large number of requests and a small startup delay.