This is a decommissioned version of ERA which is running to enable completion of migration processes. All new collections and items and all edits to existing items should go to our new ERA instance at https://ualberta.scholaris.ca - Please contact us at erahelp@ualberta.ca for assistance!
- 286 views
- 407 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