Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/70094
DC FieldValueLanguage
dc.contributorDepartment of Computing-
dc.creatorChan, WT-
dc.creatorLam, TW-
dc.creatorTing, HF-
dc.creatorWong, PWH-
dc.date.accessioned2017-11-13T02:16:40Z-
dc.date.available2017-11-13T02:16:40Z-
dc.identifier.isbn978-3-540-40176-6-
dc.identifier.isbn978-3-540-44849-5-
dc.identifier.issn0302-9743-
dc.identifier.urihttp://hdl.handle.net/10397/70094-
dc.description5th Conference on Algorithms and Complexity, CIAC 2003m Rome, Italy, May 28-30, 2003en_US
dc.language.isoenen_US
dc.publisherSpringeren_US
dc.titleOn-line stream merging, max span, and min coverageen_US
dc.typeConference Paperen_US
dc.identifier.spage70-
dc.identifier.epage82-
dc.identifier.volume2653-
dc.identifier.doi10.1007/3-540-44849-7_14-
dcterms.abstractThis 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.-
dcterms.bibliographicCitationLecture notes in computer science (including subseries Lecture notes in artificial intelligence and lecture notes in bioinformatics), 2003, v. 2653, p. 70-82-
dcterms.isPartOfLecture notes in computer science (including subseries Lecture notes in artificial intelligence and lecture notes in bioinformatics)-
dcterms.issued2003-
dc.relation.conferenceConference on Algorithms and Complexity [CIAC]-
dc.identifier.eissn1611-3349-
dc.identifier.rosgroupidr11775-
dc.description.ros2002-2003 > Academic research: refereed > Refereed conference paper-
Appears in Collections:Conference Paper
Access
View full-text via PolyU eLinks SFX Query
Show simple item record

Page view(s)

106
Last Week
6
Last month
Citations as of Jul 7, 2020

Google ScholarTM

Check

Altmetric


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