Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/70068
Title: Competitive analysis of on-line stream merging algorithms
Authors: Chan, WT
Lam, TW
Ting, HF
Wong, PWH
Issue Date: 2002
Publisher: Springer
Source: Lecture notes in computer science (including subseries Lecture notes in artificial intelligence and lecture notes in bioinformatics), 2002, v. 2420, p. 188-200 How to cite?
Journal: Lecture notes in computer science (including subseries Lecture notes in artificial intelligence and lecture notes in bioinformatics) 
Abstract: A popular approach to reduce the server bandwidth in a video-on-demand system is to merge the streams initiated at different times. In recent years, a number of on-line algorithms for stream merging have been proposed; the objective is to minimize either the total bandwidth or the maximum bandwidth over all time. The performance of these algorithms was better understood with respect to the first objective. In particular, the connector algorithm [9] is known to be O(1)-competitive, and the dyadic algorithm [12] is known to have an almost tight bounds on its average total bandwidth requirement. For minimizing maximum bandwidth, existing results are limited to empirical studies only and no algorithm has been known to be competitive. The main contribution of this paper is the first competitive analysis of the connector and the dyadic algorithms with respect to the maximum bandwidth, showing that both algorithms are 4-competitive. We also give a worst-case analysis of the dyadic algorithm with respect to the total bandwidth, revealing that the dyadic algorithm can be tuned to be 3-competitive.
Description: 27th International Symposium on Mathematical Foundations of Computer Science, MFCS 2002, Warsaw, Poland, August 26-30, 2002
URI: http://hdl.handle.net/10397/70068
ISBN: 978-3-540-44040-6
978-3-540-45687-2
ISSN: 0302-9743
EISSN: 1611-3349
DOI: 10.1007/3-540-45687-2_15
Appears in Collections:Conference Paper

Access
View full-text via PolyU eLinks SFX Query
Show full item record

Google ScholarTM

Check

Altmetric



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.