
Universität Bonn > Institut für Informatik > Abteilung V  
CSAPXReports 2003  Copyright 2003 Universität Bonn, Institut für Informatik, Abt. V  
8991 06.07.2003 
Improved Approximation Algorithms for the Quality of Service Steiner Tree Problem
Marek Karpinski, Ion I. Mandoiu, Alexander Olshevsky and Alexander Zelikovsky [Download PostScript] [Download PDF] 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 nonzero rate nodes is l * r_{e} , where r_{e} 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 nonzero 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 knownapproximation ratios of 2.667 for two nonzero rates and 5.542 forunbounded number of rates are reduced to 2.414 and 4.311, respectively. 

Last Change:
11/05/14 at 10:27:23
English 
Universität Bonn > Institut für Informatik > Abteilung V 