ERA

Download the full-sized PDF of Improved Approximation Algorithms for the Capacitated Multicast Routing ProblemDownload the full-sized PDF

Analytics

Share

Permanent link (DOI): https://doi.org/10.7939/R3C53F771

Download

Export to: EndNote  |  Zotero  |  Mendeley

Communities

This file is in the following communities:

Computing Science, Department of

Collections

This file is in the following collections:

Technical Reports (Computing Science)

Improved Approximation Algorithms for the Capacitated Multicast Routing Problem Open Access

Descriptions

Author or creator
Cai, Zhipeng
Lin, Guohui
Xue, Guoliang
Additional contributors
Subject/Keyword
Capacitated Multicast Routing
Steiner Minimum Tree
Tree Partitioning
Approximation Algorithm
Type of item
Computing Science Technical Report
Computing science technical report ID
TR04-12
Language
English
Place
Time
Description
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.
Date created
2004
DOI
doi:10.7939/R3C53F771
License information
Creative Commons Attribution 3.0 Unported
Rights

Citation for previous publication

Source
Link to related item

File Details

Date Uploaded
Date Modified
2014-04-24T22:44:36.725+00:00
Audit Status
Audits have not yet been run on this file.
Characterization
File format: pdf (Portable Document Format)
Mime type: application/pdf
File size: 237056
Last modified: 2015:10:12 21:25:29-06:00
Filename: TR04-12.pdf
Original checksum: e378e8a5b1901a30348feaedb2ece365
Well formed: true
Valid: true
File title: Improved Approximation Algorithms for the Capacitated Multicast Routing Problem
Page count: 10
Activity of users you follow
User Activity Date