This decommissioned ERA site remains active temporarily to support our final migration steps to https://ualberta.scholaris.ca, ERA's new home. All new collections and items, including Spring 2025 theses, are at that site. For assistance, please contact erahelp@ualberta.ca.
- 293 views
- 418 downloads
Improved Approximation Algorithms for the Capacitated Multicast Routing Problem
-
- Author(s) / Creator(s)
-
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
-
- Type of Item
- Report
-
- License
- Attribution 3.0 International