ERA is in the process of being migrated to Scholaris, a Canadian shared institutional repository service (https://scholaris.ca). Deposits and changes to existing ERA items and collections are frozen until migration is complete. Please contact erahelp@ualberta.ca for further assistance
- 277 views
- 393 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