File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Article: On-line stream merging in a general setting

TitleOn-line stream merging in a general setting
Authors
Chan, WTLam, TWTing, HFWong, PWH
Issue Date2003
PublisherElsevier BV. The Journal's web site is located at http://www.elsevier.com/locate/tcs
Citation
Theoretical Computer Science, 2003, v. 296 n. 1, p. 27-46 How to Cite?
DOI: http://dx.doi.org/10.1016/S0304-3975(02)00430-9
AbstractThis paper is concerned with on-line scheduling algorithms for merging streams in a video-on-demand system so as to minimize the server bandwidth. We present the first algorithm that has a constant competitive factor (precisely, 5). Our algorithm, unlike previous ones, is not limited to the scenario where clients are equipped with large buffer and client receiving bandwidth. It remains 5-competitive in all settings of buffer size and receiving bandwidth. Technically speaking, our algorithm is based on a novel observation that the behavior of any schedule can be modeled by a rectilinear (binary) tree on a grid. This observation eases the analysis of our algorithm as well as the optimal algorithm. © 2002 Elsevier Science B.V. All rights reserved.
Persistent Identifierhttp://hdl.handle.net/10722/89027
ISSN
0304-3975
2023 Impact Factor: 0.9
2023 SCImago Journal Rankings: 0.570
ISI Accession Number ID
WOS:000181125400004
References
References in Scopus

 

DC FieldValueLanguage
dc.contributor.authorChan, WTen_HK
dc.contributor.authorLam, TWen_HK
dc.contributor.authorTing, HFen_HK
dc.contributor.authorWong, PWHen_HK
dc.date.accessioned2010-09-06T09:51:28Z-
dc.date.available2010-09-06T09:51:28Z-
dc.date.issued2003en_HK
dc.identifier.citationTheoretical Computer Science, 2003, v. 296 n. 1, p. 27-46en_HK
dc.identifier.issn0304-3975en_HK
dc.identifier.urihttp://hdl.handle.net/10722/89027-
dc.description.abstractThis paper is concerned with on-line scheduling algorithms for merging streams in a video-on-demand system so as to minimize the server bandwidth. We present the first algorithm that has a constant competitive factor (precisely, 5). Our algorithm, unlike previous ones, is not limited to the scenario where clients are equipped with large buffer and client receiving bandwidth. It remains 5-competitive in all settings of buffer size and receiving bandwidth. Technically speaking, our algorithm is based on a novel observation that the behavior of any schedule can be modeled by a rectilinear (binary) tree on a grid. This observation eases the analysis of our algorithm as well as the optimal algorithm. © 2002 Elsevier Science B.V. All rights reserved.en_HK
dc.languageengen_HK
dc.publisherElsevier BV. The Journal's web site is located at http://www.elsevier.com/locate/tcsen_HK
dc.relation.ispartofTheoretical Computer Scienceen_HK
dc.rightsTheoretical Computer Science. Copyright © Elsevier BV.en_HK
dc.titleOn-line stream merging in a general settingen_HK
dc.typeArticleen_HK
dc.identifier.openurlhttp://library.hku.hk:4550/resserv?sid=HKU:IR&issn=0304-3975&volume=296&issue=1&spage=27&epage=46&date=2003&atitle=On-line+stream+merging+in+a+general+settingen_HK
dc.identifier.emailLam, TW:twlam@cs.hku.hken_HK
dc.identifier.emailTing, HF:hfting@cs.hku.hken_HK
dc.identifier.authorityLam, TW=rp00135en_HK
dc.identifier.authorityTing, HF=rp00177en_HK
dc.description.naturelink_to_subscribed_fulltext-
dc.identifier.doi10.1016/S0304-3975(02)00430-9en_HK
dc.identifier.scopuseid_2-s2.0-0037269031en_HK
dc.identifier.hkuros80437en_HK
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-0037269031&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.volume296en_HK
dc.identifier.issue1en_HK
dc.identifier.spage27en_HK
dc.identifier.epage46en_HK
dc.identifier.isiWOS:000181125400004-
dc.publisher.placeNetherlandsen_HK
dc.identifier.scopusauthoridChan, WT=7403918060en_HK
dc.identifier.scopusauthoridLam, TW=7202523165en_HK
dc.identifier.scopusauthoridTing, HF=7005654198en_HK
dc.identifier.scopusauthoridWong, PWH=9734871500en_HK
dc.identifier.issnl0304-3975-

Export via OAI-PMH Interface in XML Formats

OR

Export to Other Non-XML Formats