Competitive analysis of on-line stream merging algorithms

Wun Tat Chan; Tak Wah Lam; Hing Fung Ting; Prudence W.H. Wong

doi:10.1007/3-540-45687-2_15

Competitive analysis of on-line stream merging algorithms

Wun Tat Chan
, Tak Wah Lam
, Hing Fung Ting
, Prudence W.H. Wong

School of Continuing Education

Research output: Chapter in book/report/conference proceeding › Conference proceeding › peer-review

7 Citations (Scopus)

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 online 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 worstcase analysis of the dyadic algorithm with respect to the total bandwidth, revealing that the dyadic algorithm can be tuned to be 3-competitive.

Original language	English
Title of host publication	Mathematical Foundations of Computer Science 2002
Subtitle of host publication	27th International Symposium, MFCS 2002, Warsaw, Poland, August 26-30, 2002. Proceedings
Editors	Krzysztof Diks, Wojciech Rytter
Place of Publication	Heidelberg
Publisher	Springer Berlin Heidelberg
Pages	188-200
Number of pages	13
ISBN (Electronic)	9783540456872
ISBN (Print)	3540440402, 9783540440406
DOIs	https://doi.org/10.1007/3-540-45687-2_15
Publication status	Published - 14 Aug 2002
Event	27th International Symposium on Mathematical Foundations of Computer Science - Warsaw, Poland Duration: 26 Aug 2002 → 30 Aug 2002 https://link.springer.com/book/10.1007/3-540-45687-2#overview (Conference proceeding)

Publication series

Name	Lecture Notes in Computer Science
Volume	2420
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Name	International Symposium on Mathematical Foundations of Computer Science

Conference

Conference	27th International Symposium on Mathematical Foundations of Computer Science
Abbreviated title	MFCS 2002
Country/Territory	Poland
City	Warsaw
Period	26/08/02 → 30/08/02
Internet address	https://link.springer.com/book/10.1007/3-540-45687-2#overview (Conference proceeding)

UN SDGs

This output contributes to the following UN Sustainable Development Goals (SDGs)

SDG 9 Industry, Innovation, and Infrastructure

User-Defined Keywords

Competitive Ratio
Total Bandwidth
Competitive Analysis
Maximum Bandwidth
Broadcasting Scheme

Access to Document

10.1007/3-540-45687-2_15

Cite this

Chan, W. T., Lam, T. W., Ting, H. F., & Wong, P. W. H. (2002). Competitive analysis of on-line stream merging algorithms. In K. Diks, & W. Rytter (Eds.), Mathematical Foundations of Computer Science 2002: 27th International Symposium, MFCS 2002, Warsaw, Poland, August 26-30, 2002. Proceedings (pp. 188-200). (Lecture Notes in Computer Science; Vol. 2420), (International Symposium on Mathematical Foundations of Computer Science). Springer Berlin Heidelberg. https://doi.org/10.1007/3-540-45687-2_15

Chan, Wun Tat ; Lam, Tak Wah ; Ting, Hing Fung et al. / Competitive analysis of on-line stream merging algorithms. Mathematical Foundations of Computer Science 2002: 27th International Symposium, MFCS 2002, Warsaw, Poland, August 26-30, 2002. Proceedings. editor / Krzysztof Diks ; Wojciech Rytter. Heidelberg : Springer Berlin Heidelberg, 2002. pp. 188-200 (Lecture Notes in Computer Science). (International Symposium on Mathematical Foundations of Computer Science).

@inproceedings{e9c1e94d53f74f8cbe64d9a6151226c1,

title = "Competitive analysis of on-line stream merging algorithms",

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 online 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 worstcase analysis of the dyadic algorithm with respect to the total bandwidth, revealing that the dyadic algorithm can be tuned to be 3-competitive.",

keywords = "Competitive Ratio, Total Bandwidth, Competitive Analysis, Maximum Bandwidth, Broadcasting Scheme",

author = "Chan, \{Wun Tat\} and Lam, \{Tak Wah\} and Ting, \{Hing Fung\} and Wong, \{Prudence W.H.\}",

note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 2002.; 27th International Symposium on Mathematical Foundations of Computer Science, MFCS 2002 ; Conference date: 26-08-2002 Through 30-08-2002",

year = "2002",

month = aug,

day = "14",

doi = "10.1007/3-540-45687-2\_15",

language = "English",

isbn = "3540440402",

series = "Lecture Notes in Computer Science",

publisher = "Springer Berlin Heidelberg",

pages = "188--200",

editor = "Krzysztof Diks and Wojciech Rytter",

booktitle = "Mathematical Foundations of Computer Science 2002",

url = "https://link.springer.com/book/10.1007/3-540-45687-2\#overview",

}

Chan, WT, Lam, TW, Ting, HF & Wong, PWH 2002, Competitive analysis of on-line stream merging algorithms. in K Diks & W Rytter (eds), Mathematical Foundations of Computer Science 2002: 27th International Symposium, MFCS 2002, Warsaw, Poland, August 26-30, 2002. Proceedings. Lecture Notes in Computer Science, vol. 2420, International Symposium on Mathematical Foundations of Computer Science, Springer Berlin Heidelberg, Heidelberg, pp. 188-200, 27th International Symposium on Mathematical Foundations of Computer Science, Warsaw, Poland, 26/08/02. https://doi.org/10.1007/3-540-45687-2_15

Competitive analysis of on-line stream merging algorithms. / Chan, Wun Tat; Lam, Tak Wah; Ting, Hing Fung et al.
Mathematical Foundations of Computer Science 2002: 27th International Symposium, MFCS 2002, Warsaw, Poland, August 26-30, 2002. Proceedings. ed. / Krzysztof Diks; Wojciech Rytter. Heidelberg: Springer Berlin Heidelberg, 2002. p. 188-200 (Lecture Notes in Computer Science; Vol. 2420), (International Symposium on Mathematical Foundations of Computer Science).

Research output: Chapter in book/report/conference proceeding › Conference proceeding › peer-review

TY - GEN

T1 - Competitive analysis of on-line stream merging algorithms

AU - Chan, Wun Tat

AU - Lam, Tak Wah

AU - Ting, Hing Fung

AU - Wong, Prudence W.H.

N1 - Publisher Copyright: © Springer-Verlag Berlin Heidelberg 2002.

PY - 2002/8/14

Y1 - 2002/8/14

N2 - 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 online 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 worstcase analysis of the dyadic algorithm with respect to the total bandwidth, revealing that the dyadic algorithm can be tuned to be 3-competitive.

AB - 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 online 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 worstcase analysis of the dyadic algorithm with respect to the total bandwidth, revealing that the dyadic algorithm can be tuned to be 3-competitive.

KW - Competitive Ratio

KW - Total Bandwidth

KW - Competitive Analysis

KW - Maximum Bandwidth

KW - Broadcasting Scheme

UR - https://www.scopus.com/pages/publications/84956991084

UR - https://link.springer.com/chapter/10.1007/3-540-45687-2_15#publish-with-us

U2 - 10.1007/3-540-45687-2_15

DO - 10.1007/3-540-45687-2_15

M3 - Conference proceeding

AN - SCOPUS:84956991084

SN - 3540440402

SN - 9783540440406

T3 - Lecture Notes in Computer Science

SP - 188

EP - 200

BT - Mathematical Foundations of Computer Science 2002

A2 - Diks, Krzysztof

A2 - Rytter, Wojciech

PB - Springer Berlin Heidelberg

CY - Heidelberg

T2 - 27th International Symposium on Mathematical Foundations of Computer Science

Y2 - 26 August 2002 through 30 August 2002

ER -

Chan WT, Lam TW, Ting HF, Wong PWH. Competitive analysis of on-line stream merging algorithms. In Diks K, Rytter W, editors, Mathematical Foundations of Computer Science 2002: 27th International Symposium, MFCS 2002, Warsaw, Poland, August 26-30, 2002. Proceedings. Heidelberg: Springer Berlin Heidelberg. 2002. p. 188-200. (Lecture Notes in Computer Science). (International Symposium on Mathematical Foundations of Computer Science). Epub 2002 Jan 1. doi: 10.1007/3-540-45687-2_15

Competitive analysis of on-line stream merging algorithms

Abstract

Publication series

Conference

UN SDGs

User-Defined Keywords

Access to Document

Other files and links

Fingerprint

Cite this