An improved approximation algorithm for multicast k-tree routing

被引：8
|
作者：
Lin, GH [1 ]
机构：
[1] Univ Alberta, Dept Comp Sci, Edmonton, AB T6G 2E8, Canada
来源：
JOURNAL OF COMBINATORIAL OPTIMIZATION | 2005年 / 9卷 / 04期
基金：
加拿大创新基金会; 加拿大自然科学与工程研究理事会; 中国国家自然科学基金;
关键词：
approximation algorithm; multicast k-tree routing; Steiner minimum tree; weight averaging; tree partitioning;
D O I：
10.1007/s10878-005-1776-x
中图分类号：
TP39 [计算机的应用];
学科分类号：
081203 ; 0835 ;
摘要：
An improved approximation algorithm is presented in this paper for the multicast k-tree routing problem. The algorithm has a worst case performance ratio of (2.4 + rho), where rho is the best approximation ratio for the metric Steiner tree problem (and is about 1.55 so far). The previous best approximation algorithm for the multicast k-tree routing problem has a performance ratio of 4. Two techniques, weight averaging and tree partitioning, are developed to facilitate the algorithm design and analysis.
引用
收藏
页码：349 / 356
页数：8
相关论文
共 50 条
  • [1] An Improved Approximation Algorithm for Multicast k-Tree Routing
    Guohui Lin
    Journal of Combinatorial Optimization, 2005, 9 : 349 - 356
  • [2] Size-Constrained Tree Partitioning: A Story on Approximation Algorithm Design for the Multicast k-Tree Routing Problem
    Cai, Zhipeng
    Goebel, Randy
    Lin, Guohui
    COMBINATORIAL OPTIMIZATION AND APPLICATIONS, PROCEEDINGS, 2009, 5573 : 363 - 374
  • [3] An improved approximation algorithm for the capacitated multicast tree routing problem
    Cai, Zhipeng
    Chen, Zhi-Zhong
    Lin, Guohui
    Wang, Lusheng
    COMBINATORIAL OPTIMIZATION AND APPLICATIONS, PROCEEDINGS, 2008, 5165 : 286 - +
  • [4] Size-constrained tree partitioning: Approximating the multicast k-tree routing problem
    Cai, Zhipeng
    Goebel, Randy
    Lin, Guohui
    THEORETICAL COMPUTER SCIENCE, 2011, 412 (03) : 240 - 245
  • [5] The extended k-tree algorithm
    Minder, Lorenz
    Sinclair, Alistair
    PROCEEDINGS OF THE TWENTIETH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, 2009, : 586 - 595
  • [6] The Extended k-tree Algorithm
    Minder, Lorenz
    Sinclair, Alistair
    JOURNAL OF CRYPTOLOGY, 2012, 25 (02) : 349 - 382
  • [7] The Extended k-tree Algorithm
    Lorenz Minder
    Alistair Sinclair
    Journal of Cryptology, 2012, 25 : 349 - 382
  • [8] Approximation algorithms for 2-source minimum routing cost k-tree problems
    Chen, Yen Hung
    Liao, Gwo-Liang
    Tang, Chuan Yi
    COMPUTATIONAL SCIENCE AND ITS APPLICATIONS - ICCSA 2007, PT 3, PROCEEDINGS, 2007, 4707 : 520 - +
  • [9] A 3.4713-approximation algorithm for the capacitated multicast tree routing problem
    Cai, Zhipeng
    Chen, Zhi-Zhong
    Lin, Guohui
    THEORETICAL COMPUTER SCIENCE, 2009, 410 (52) : 5415 - 5424
  • [10] Stronger K-tree relaxations for the vehicle routing problem
    Martinhon, C
    Lucena, A
    Maculan, N
    EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2004, 158 (01) : 56 - 71
12345