检索结果-内蒙古大学图书馆

A 3.4713-approximation algorithm for the capacitated multicast tree routing problem

THEORETICAL COMPUTER SCIENCE 2009年第52期410卷 5415-5424页

作者： Cai, Zhipeng Chen, Zhi-Zhong Lin, Guohui Univ Alberta Dept Comp Sci Edmonton AB T6G 2E8 Canada Tokyo Denki Univ Dept Math Sci Hatoyama Saitama 3500394 Japan

Given an underlying communication network represented as an edge-weighted graph G = (V, E), a source node S is an element of V, a set of destination nodes D subset of V, and a capacity k which is a positive integer, the capacitated multicast tree routing problem asks for a minimum cost routing scheme for source s to send data to all destination nodes, under the constraint that in each routing tree at most k destination nodes are allowed to receive the data copies. The cost of the routing scheme is the sum of the costs of all individual routing trees therein. Improving on Our previous approximation algorithm for the problem, we present a new algorithm which achieves a worst case performance ratio of root 2089+77/80 + 5/4 rho, where rho denotes the best known approximation ratio for the Steiner minimum tree problem. Since rho is about 1.55 at the writing of the paper, the ratio achieved by Our new algorithm is less than 3.4713. In comparison, the previously best ratio Was 8/5 + 5/4 rho approximate to 3.5375. (C) 2009 Elsevier B.V. All rights reserved.

关键词： capacitated multicast tree routing Approximation algorithm Steiner minimum tree tree partitioning

来源：评论

学校读者我要写书评

暂无评论

An improved approximation algorithm for the capacitated multicast tree routing problem

引用

2nd International Conference on Combinatorial Optimization and Applications

作者： Cai, Zhipeng Chen, Zhi-Zhong Lin, Guohui Wang, Lusheng Univ Alberta Dept Comp Sci Edmonton AB T6G 2E8 Canada Tokyo Denki Univ Dept Math Sci Hatoyama Saitama 35003 Japan City Univ Hong Kong Dept Comp Sci Kowloon Peoples R China

ISBN: (纸本)9783540850960

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 8/5 + 5/4 rho. Here rho 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+rho.

关键词： capacitated multicast tree routing approximation algorithm Steiner Minimum tree tree partitioning

来源：评论

学校读者我要写书评

暂无评论

Size-constrained tree partitioning: Approximating the multicast k-tree routing problem

引用

THEORETICAL COMPUTER SCIENCE 2011年第3期412卷 240-245页

作者： Cai, Zhipeng Goebel, Randy Lin, Guohui Univ Alberta Dept Comp Sci Edmonton AB T6G 2E8 Canada

In the multicast k-tree routing problem, a data copy is sent from the source node to at most k destination nodes in every transmission. The goal is to minimize the total cost of sending data to all destination nodes, which is measured as the sum of the costs of all routing trees. This problem was formulated out of optical networking and has applications in general multicasting. Several approximation algorithms, with increasing performance, have been proposed in the last several years;the most recent ones rely heavily on a tree partitioning technique. In this paper, we present a further improved approximation algorithm along the line. The algorithm has a worst-case performance ratio of 5/4 rho + 3/2, where rho denotes the best approximation ratio for the Steiner minimum tree problem. The proofs of the technical routing lemmas also provide some insights into why such a performance ratio could be the best possible that one can get using this tree partitioning technique. (C) 2009 Elsevier B.V. All rights reserved.

关键词： capacitated multicast tree routing Approximation algorithm tree partitioning

来源：评论

学校读者我要写书评

暂无评论

Size-constrained tree partitioning: Approximating the multicast k-tree routing problem

Size-constrained tree partitioning: Approximating the multic...

引用

3rd International Conference on Combinatorial Optimization and Applications (COCOA 2009)

作者： Cai, Zhipeng Goebel, Randy Lin, Guohui Univ Alberta Dept Comp Sci Edmonton AB T6G 2E8 Canada

关键词： capacitated multicast tree routing Approximation algorithm tree partitioning

来源：评论

学校读者我要写书评

暂无评论

Size-Constrained tree Partitioning: A Story on Approximation Algorithm Design for the multicast k-tree routing Problem

Size-Constrained Tree Partitioning: A Story on Approximation...

引用

3rd International Conference on Combinatorial Optimization and Applications (COCOA 2009)

作者： Cai, Zhipeng Goebel, Randy Lin, Guohui Univ Alberta Dept Comp Sci Edmonton AB T6G 2E8 Canada

ISBN: (纸本)9783642020254

In the multicast k-tree routing Problem, a data copy is sent from the source node to at most k destination nodes in every transmission. The goal is to minimize the total cost of sending data to all destination nodes, which is measured as the sum of the costs of all routing trees. This problem was formulated Out of optical networking and has applications in general multicasting. Several approximation algorithms, with increasing performance, have been proposed in the last several years;The most recent ones are heavily relied on a tree partitioning technique. In this paper, we present a further improved approximation algorithm along the line. The algorithm has a worst case performance ratio of 5/4 rho + 3/2, where p denotes the best approximation ratio for the Steiner Minimum tree problem. The proofs of the technical routing lemmas also provide some insights on why such a performance ratio could be the best possible that one can get using this tree partitioning technique.

关键词： capacitated multicast tree routing Approximation Algorithm tree Partitioning

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：