An Improved Approximation Algorithm for the Capacitated Multicast Tree Routing Problem

• Author(s) / Creator(s)

  • Cai, Zhipeng
  • Lin, Guohui
  • Want, Lusheng
  • Chen, Zhi-Zhong

• Technical report TR08-06. 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ρ. 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 + ρ. | TRID-ID TR08-06

• Date created

  2008

• Subjects / Keywords

  • Approximation algorithms
  • Capacitated multicast routing
  • Steiner minimum tree
  • Tree partitioning

• Type of Item

  Report

• DOI

  https://doi.org/10.7939/R3H12VF0S

• License

  Attribution 3.0 International