Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/70094
Title: On-line stream merging, max span, and min coverage
Authors: Chan, WT
Lam, TW
Ting, HF
Wong, PWH
Issue Date: 2003
Publisher: Springer
Source: Lecture notes in computer science (including subseries Lecture notes in artificial intelligence and lecture notes in bioinformatics), 2003, v. 2653, p. 70-82 How to cite?
Journal: Lecture notes in computer science (including subseries Lecture notes in artificial intelligence and lecture notes in bioinformatics) 
Abstract: This paper introduces the notions of span and coverage for analyzing the performance of on-line algorithms for stream merging. We show that these two notions can solely determine the competitive ratio of any such algorithm. Furthermore, we devise a simple greedy algorithm that can attain the ideal span and coverage, thus giving a better performance guarantee than existing algorithms with respect to either the maximum bandwidth or the total bandwidth. The new notions also allow us to obtain a tighter analysis of existing algorithms.
Description: 5th Conference on Algorithms and Complexity, CIAC 2003m Rome, Italy, May 28-30, 2003
URI: http://hdl.handle.net/10397/70094
ISBN: 978-3-540-40176-6
978-3-540-44849-5
ISSN: 0302-9743
EISSN: 1611-3349
DOI: 10.1007/3-540-44849-7_14
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.