Improved Approximation Algorithms for the Quality of Service Multicast Tree Problem

Free registration required

Executive Summary

This paper has considered a generalization of the Steiner problem in which each node possesses a rate and the cost of an edge. This paper have given improved approximation algorithms finding trees with a cost at most 1.960 (Respectively 3.802) times the minimum cost for the case of two (Respectively Unbounded Number Of) non-zero rates. The improvement is based on the analysis of the gain resulting from the reuse of higher rate edges in the connectivity of the lower rate edges.

  • Format: PDF
  • Size: 153.7 KB