File Download
There are no files associated with this item.
Links for fulltext
(May Require Subscription)
- Publisher Website: 10.1016/S0304-3975(02)00430-9
- Scopus: eid_2-s2.0-0037269031
- WOS: WOS:000181125400004
- Find via
Supplementary
- Citations:
- Appears in Collections:
Article: On-line stream merging in a general setting
Title | On-line stream merging in a general setting |
---|---|
Authors | |
Issue Date | 2003 |
Publisher | Elsevier 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? |
Abstract | This 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 Identifier | http://hdl.handle.net/10722/89027 |
ISSN | 2023 Impact Factor: 0.9 2023 SCImago Journal Rankings: 0.570 |
ISI Accession Number ID | |
References |
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Chan, WT | en_HK |
dc.contributor.author | Lam, TW | en_HK |
dc.contributor.author | Ting, HF | en_HK |
dc.contributor.author | Wong, PWH | en_HK |
dc.date.accessioned | 2010-09-06T09:51:28Z | - |
dc.date.available | 2010-09-06T09:51:28Z | - |
dc.date.issued | 2003 | en_HK |
dc.identifier.citation | Theoretical Computer Science, 2003, v. 296 n. 1, p. 27-46 | en_HK |
dc.identifier.issn | 0304-3975 | en_HK |
dc.identifier.uri | http://hdl.handle.net/10722/89027 | - |
dc.description.abstract | This 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.language | eng | en_HK |
dc.publisher | Elsevier BV. The Journal's web site is located at http://www.elsevier.com/locate/tcs | en_HK |
dc.relation.ispartof | Theoretical Computer Science | en_HK |
dc.rights | Theoretical Computer Science. Copyright © Elsevier BV. | en_HK |
dc.title | On-line stream merging in a general setting | en_HK |
dc.type | Article | en_HK |
dc.identifier.openurl | http://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+setting | en_HK |
dc.identifier.email | Lam, TW:twlam@cs.hku.hk | en_HK |
dc.identifier.email | Ting, HF:hfting@cs.hku.hk | en_HK |
dc.identifier.authority | Lam, TW=rp00135 | en_HK |
dc.identifier.authority | Ting, HF=rp00177 | en_HK |
dc.description.nature | link_to_subscribed_fulltext | - |
dc.identifier.doi | 10.1016/S0304-3975(02)00430-9 | en_HK |
dc.identifier.scopus | eid_2-s2.0-0037269031 | en_HK |
dc.identifier.hkuros | 80437 | en_HK |
dc.relation.references | http://www.scopus.com/mlt/select.url?eid=2-s2.0-0037269031&selection=ref&src=s&origin=recordpage | en_HK |
dc.identifier.volume | 296 | en_HK |
dc.identifier.issue | 1 | en_HK |
dc.identifier.spage | 27 | en_HK |
dc.identifier.epage | 46 | en_HK |
dc.identifier.isi | WOS:000181125400004 | - |
dc.publisher.place | Netherlands | en_HK |
dc.identifier.scopusauthorid | Chan, WT=7403918060 | en_HK |
dc.identifier.scopusauthorid | Lam, TW=7202523165 | en_HK |
dc.identifier.scopusauthorid | Ting, HF=7005654198 | en_HK |
dc.identifier.scopusauthorid | Wong, PWH=9734871500 | en_HK |
dc.identifier.issnl | 0304-3975 | - |