Please use this identifier to cite or link to this item:
Title: Competitive analysis of on-line stream merging algorithms
Authors: Chan, WT
Lam, TW
Ting, HF
Wong, PWH
Issue Date: 2002
Source: Lecture notes in computer science (including subseries Lecture notes in artificial intelligence and lecture notes in bioinformatics), 2002, v. 2420, p. 188-200
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.
Publisher: Springer
Journal: Lecture notes in computer science (including subseries Lecture notes in artificial intelligence and lecture notes in bioinformatics) 
ISBN: 978-3-540-44040-6
ISSN: 0302-9743
EISSN: 1611-3349
DOI: 10.1007/3-540-45687-2_15
Description: 27th International Symposium on Mathematical Foundations of Computer Science, MFCS 2002, Warsaw, Poland, August 26-30, 2002
Appears in Collections:Conference Paper

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


Last Week
Last month
Citations as of Aug 14, 2020

Page view(s)

Last Week
Last month
Citations as of Sep 21, 2020

Google ScholarTM



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