ERA

Download the full-sized PDF of An Improved Approximation Algorithm for the Capacitated Multicast Tree Routing ProblemDownload the full-sized PDF

Analytics

Share

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

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)

An Improved Approximation Algorithm for the Capacitated Multicast Tree Routing Problem Open Access

Descriptions

Author or creator
Cai, Zhipeng
Chen, Zhi-Zhong
Lin, Guohui
Want, Lusheng
Additional contributors
Subject/Keyword
Capacitated multicast routing
Steiner minimum tree
Approximation algorithm
Tree partitioning
Type of item
Computing Science Technical Report
Computing science technical report ID
TR08-06
Language
English
Place
Time
Description
Technical report TR08-06. The Capacitated Multicast Tree Routing Problem is considered, in which only a limited number of destination nodes are allowed to receive data in one routing tree and multiple routing trees are needed to send data from the source node to all destination nodes. The goal is to minimize the total cost of these routing trees. An improved approximation algorithm is presented, which has a worst case performance ratio of 8/5 + 5/4ρ. Here ρ denotes the best approximation ratio for the Steiner Minimum Tree problem, and it is about 1.55 at the writing of the paper. This improves upon the previous best having a performance ratio of 2 + ρ.
Date created
2008
DOI
doi:10.7939/R3H12VF0S
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-05-02T17:42:13.629+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: 272808
Last modified: 2015:10:12 21:06:21-06:00
Filename: TR08-06.pdf
Original checksum: 6720433247d3600b3d2af8c084171968
Well formed: true
Valid: true
File title: Introduction
Page count: 14
Activity of users you follow
User Activity Date