Improved Approximation Algorithms for the Capacitated Multicast Routing Problem

• Author(s) / Creator(s)

  • Cai, Zhipeng
  • Lin, Guohui
  • Xue, Guoliang

• Technical report TR04-12. For the Capacitated Multicast Routing Problem, we considered two models which are the Multicast k-Path Routing and the Multicast k-Tree Routing. We presented two improved approximation algorithms for them, which have worst case performance ratios of 3 and (2 + ρ) (ρ is the best approximation ratio for the Steiner Tree problem, and is about 1.55), respectively, thus improving upon the previous best ones having performance ratios of 4 and (2.4 + ρ), respectively. The designing techniques developed in the paper could be applicable to other similar networking problems. | TRID-ID TR04-12

• Date created

  2004

• Subjects / Keywords

  • Steiner Minimum Tree
  • Tree Partitioning
  • Approximation algorithms
  • Capacitated Multicast Routing

• Type of Item

  Report

• DOI

  https://doi.org/10.7939/R3C53F771

• License

  Attribution 3.0 International