Quality of Service Multicast Tree

• INSTANCE: Graph $G =(V,E,l,r)$ , the length function on each edge $l : E \rightarrow R_+$ , the rate function on each node $r : V \rightarrow R_+$ , source $s$ , sets $S_i$ of terminals with rate $r_i$

• SOLUTION: A tree $T=(V_T, E_T, l,r)$ spanning all terminals.

• COST FUNCTION: $\sum_{e \in E_T} l(e)r_e$ , where $r_e = max(r_i, r_j)$ .

• OBJECTIVE: Minimize.

• Approx.: Approximable within 3.802 [72]

• Hardness: NP-hard to within an approximation ratio 96/95 [36].

• Comment: Approximable within 1.960 for two non-zero rates.