Resource Optimization in QoS Multicast Routing of Real-Time Multimedia 

We consider a network design problem, where applications require various levels of Quality-of-Service (QoS) while connections have limited performance. Suppose that a source needs to send a message to a heterogeneous set of
receivers. The objective is to design a low cost multicast tree from the source that would provide the QoS levels (e.g., bandwidth) requested by the receivers. We assume that the QoS level required on a link is the maximum among the
QoS levels of the receivers that are connected to the source through the link. In accordance, we define the cost of a link to be a function of the QoS level that it provides. This definition of cost makes this optimization 
problem more general than the classical Steiner tree problem. We consider several variants of this problem all of which are proved to be NP-hard. For the variant where QoS levels of a link can vary arbitrarily and the cost function is
linear in its QoS level, we give a heuristic that achieves a multicast tree with cost at most a constant 
times the cost of an optimal multicast tree. The constant depends on the best constant approximation ratio of the classical Steiner tree problem. For the more general variant, where each link has a given QoS level and cost we present
a heuristic that generates a multicast tree with cost O(min{log r, k}) times the cost of an optimal tree, where r denotes the number of receivers, and k denotes the number of different levels of QoS required. We generalize this result to
hold for the case of many multicast groups. 

This is joint work with Moses Charikar and Joseph (Seffi) Naor.