An improved approximation algorithm for the capacitated multicast tree routing problem

Zhipeng Cai; Zhi-Zhong Chen; Guohui Lin; Lusheng Wang

doi:10.1007/978-3-540-85097-7_27

An improved approximation algorithm for the capacitated multicast tree routing problem

Zhipeng Cai, Zhi-Zhong Chen, Guohui Lin^*, Lusheng Wang

^*Corresponding author for this work

Department of Computer Science

Research output: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review

15 Citations (Scopus)

Abstract

The Capacitated Multicast Tree Routing Problem is considered, in which only a limited number of destination nodes are allowed to receive data in one routing tree and multiple routing trees are needed to send data from the source node to all destination nodes. The goal is to minimize the total cost of these routing trees. An improved approximation algorithm is presented, which has a worst case performance ratio of . Here ρ denotes the best approximation ratio for the Steiner Minimum Tree problem, and it is about 1.55 at the writing of the paper. This improves upon the previous best having a performance ratio of 2∈+∈ρ. © Springer-Verlag Berlin Heidelberg 2008.

Original language	English
Title of host publication	Combinatorial Optimization and Applications
Subtitle of host publication	Second International Conference, COCOA 2008, Proceedings
Publisher	Springer Verlag
Pages	286-295
Volume	5165 LNCS
ISBN (Print)	3540850961, 9783540850960
DOIs	https://doi.org/10.1007/978-3-540-85097-7_27
Publication status	Published - 2008
Event	2nd International Conference on Combinatorial Optimization and Applications, COCOA 2008 - St. John's, NL, Canada Duration: 21 Aug 2008 → 24 Aug 2008

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	5165 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	2nd International Conference on Combinatorial Optimization and Applications, COCOA 2008
Country/Territory	Canada
City	St. John's, NL
Period	21/08/08 → 24/08/08

Research Keywords

Approximation algorithm
Capacitated multicast tree routing
Steiner minimum tree
Tree partitioning

Access Output

10.1007/978-3-540-85097-7_27

Other Access Options

Check CityUHK Library

Permanent Link

Right click to copy link

Cite this

Cai, Z., Chen, Z.-Z., Lin, G., & Wang, L. (2008). An improved approximation algorithm for the capacitated multicast tree routing problem. In Combinatorial Optimization and Applications: Second International Conference, COCOA 2008, Proceedings (Vol. 5165 LNCS, pp. 286-295). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5165 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-540-85097-7_27

Cai, Zhipeng ; Chen, Zhi-Zhong ; Lin, Guohui et al. / An improved approximation algorithm for the capacitated multicast tree routing problem. Combinatorial Optimization and Applications: Second International Conference, COCOA 2008, Proceedings. Vol. 5165 LNCS Springer Verlag, 2008. pp. 286-295 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{f627b69a081549ff8d6c1d82dabd6dc6,

title = "An improved approximation algorithm for the capacitated multicast tree routing problem",

abstract = "The Capacitated Multicast Tree Routing Problem is considered, in which only a limited number of destination nodes are allowed to receive data in one routing tree and multiple routing trees are needed to send data from the source node to all destination nodes. The goal is to minimize the total cost of these routing trees. An improved approximation algorithm is presented, which has a worst case performance ratio of . Here ρ denotes the best approximation ratio for the Steiner Minimum Tree problem, and it is about 1.55 at the writing of the paper. This improves upon the previous best having a performance ratio of 2∈+∈ρ. {\textcopyright} Springer-Verlag Berlin Heidelberg 2008.",

keywords = "Approximation algorithm, Capacitated multicast tree routing, Steiner minimum tree, Tree partitioning",

author = "Zhipeng Cai and Zhi-Zhong Chen and Guohui Lin and Lusheng Wang",

year = "2008",

doi = "10.1007/978-3-540-85097-7_27",

language = "English",

isbn = "3540850961",

volume = "5165 LNCS",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "286--295",

booktitle = "Combinatorial Optimization and Applications",

address = "Germany",

note = "2nd International Conference on Combinatorial Optimization and Applications, COCOA 2008 ; Conference date: 21-08-2008 Through 24-08-2008",

}

Cai, Z, Chen, Z-Z, Lin, G & Wang, L 2008, An improved approximation algorithm for the capacitated multicast tree routing problem. in Combinatorial Optimization and Applications: Second International Conference, COCOA 2008, Proceedings. vol. 5165 LNCS, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 5165 LNCS, Springer Verlag, pp. 286-295, 2nd International Conference on Combinatorial Optimization and Applications, COCOA 2008, St. John's, NL, Canada, 21/08/08. https://doi.org/10.1007/978-3-540-85097-7_27

An improved approximation algorithm for the capacitated multicast tree routing problem. / Cai, Zhipeng; Chen, Zhi-Zhong; Lin, Guohui et al.
Combinatorial Optimization and Applications: Second International Conference, COCOA 2008, Proceedings. Vol. 5165 LNCS Springer Verlag, 2008. p. 286-295 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5165 LNCS).

Research output: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review

TY - GEN

T1 - An improved approximation algorithm for the capacitated multicast tree routing problem

AU - Cai, Zhipeng

AU - Chen, Zhi-Zhong

AU - Lin, Guohui

AU - Wang, Lusheng

PY - 2008

Y1 - 2008

N2 - The Capacitated Multicast Tree Routing Problem is considered, in which only a limited number of destination nodes are allowed to receive data in one routing tree and multiple routing trees are needed to send data from the source node to all destination nodes. The goal is to minimize the total cost of these routing trees. An improved approximation algorithm is presented, which has a worst case performance ratio of . Here ρ denotes the best approximation ratio for the Steiner Minimum Tree problem, and it is about 1.55 at the writing of the paper. This improves upon the previous best having a performance ratio of 2∈+∈ρ. © Springer-Verlag Berlin Heidelberg 2008.

AB - The Capacitated Multicast Tree Routing Problem is considered, in which only a limited number of destination nodes are allowed to receive data in one routing tree and multiple routing trees are needed to send data from the source node to all destination nodes. The goal is to minimize the total cost of these routing trees. An improved approximation algorithm is presented, which has a worst case performance ratio of . Here ρ denotes the best approximation ratio for the Steiner Minimum Tree problem, and it is about 1.55 at the writing of the paper. This improves upon the previous best having a performance ratio of 2∈+∈ρ. © Springer-Verlag Berlin Heidelberg 2008.

KW - Approximation algorithm

KW - Capacitated multicast tree routing

KW - Steiner minimum tree

KW - Tree partitioning

UR - http://www.scopus.com/inward/record.url?scp=51849092959&partnerID=8YFLogxK

UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-51849092959&origin=recordpage

U2 - 10.1007/978-3-540-85097-7_27

DO - 10.1007/978-3-540-85097-7_27

M3 - RGC 32 - Refereed conference paper (with host publication)

SN - 3540850961

SN - 9783540850960

VL - 5165 LNCS

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 286

EP - 295

BT - Combinatorial Optimization and Applications

PB - Springer Verlag

T2 - 2nd International Conference on Combinatorial Optimization and Applications, COCOA 2008

Y2 - 21 August 2008 through 24 August 2008

ER -

Cai Z, Chen ZZ, Lin G, Wang L. An improved approximation algorithm for the capacitated multicast tree routing problem. In Combinatorial Optimization and Applications: Second International Conference, COCOA 2008, Proceedings. Vol. 5165 LNCS. Springer Verlag. 2008. p. 286-295. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-540-85097-7_27

An improved approximation algorithm for the capacitated multicast tree routing problem

Abstract

Publication series

Conference

Research Keywords

Access Output

Other Access Options

Permanent Link

Other Files and Links

Fingerprint

Cite this