TY - CHAP
T1 - Improved approximation algorithms for the Quality of Service Steiner Tree Problem
AU - Karpinski, Marek
AU - Mǎndoiu, Ion I.
AU - Olshevsky, Alexander
AU - Zelikovsky, Alexander
PY - 2003
Y1 - 2003
N2 - The Quality of Service Steiner Tree Problem is a generalization of the Steiner problem which appears in the context of multimedia multicast and network design. In this generalization, each node possesses a rate and the cost of an edge with length l in a Steiner tree T connecting the non-zero rate nodes is l·re, where re is the maximum rate in the component of T - {e} that does not contain the source. The best previously known approximation ratios for this problem (based on the best known approximation factor of 1.549 for the Steiner tree problem in networks) are 2.066 for the case of two non-zero rates and 4.211 for the case of unbounded number of rates. We give better approximation algorithms with ratios of 1.960 and 3.802, respectively. When the minimum spanning tree heuristic is used for finding approximate Steiner trees, then the previously best known approximation ratios of 2.667 for two non-zero rates and 5.542 for unbounded number of rates are reduced to 2.414 and 4.311, respectively.
AB - The Quality of Service Steiner Tree Problem is a generalization of the Steiner problem which appears in the context of multimedia multicast and network design. In this generalization, each node possesses a rate and the cost of an edge with length l in a Steiner tree T connecting the non-zero rate nodes is l·re, where re is the maximum rate in the component of T - {e} that does not contain the source. The best previously known approximation ratios for this problem (based on the best known approximation factor of 1.549 for the Steiner tree problem in networks) are 2.066 for the case of two non-zero rates and 4.211 for the case of unbounded number of rates. We give better approximation algorithms with ratios of 1.960 and 3.802, respectively. When the minimum spanning tree heuristic is used for finding approximate Steiner trees, then the previously best known approximation ratios of 2.667 for two non-zero rates and 5.542 for unbounded number of rates are reduced to 2.414 and 4.311, respectively.
UR - http://www.scopus.com/inward/record.url?scp=35248894881&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=35248894881&partnerID=8YFLogxK
U2 - 10.1007/978-3-540-45078-8_35
DO - 10.1007/978-3-540-45078-8_35
M3 - Chapter
AN - SCOPUS:35248894881
SN - 3540405453
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 401
EP - 411
BT - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
A2 - Dehne, Frank
A2 - Sack, Jorg-Rudiger
A2 - Smid, Michiel
PB - Springer
ER -