Quality of Service Multicast Tree Problem

• INSTANCE: Graph $G =(V,E,l,r)$ , source $s \in V$ , sets of terminals $S_0,...,S_N$ with node rates $r_0,...,r_N$ and edge lengths $l: E \rightarrow\mathbb{R}^+$ .
• SOLUTION: A tree $T = (V_T, E_T)$ in $G$ such that $\bigcup_{i\geq1}S_{i} \subseteq V_T \subseteq V$ , $E_{T} \subseteq E$ .
• COST FUNCTION: $\sum_{e \in E_{T}}c(e)$ , where $c(e)=l(e)r_e$ (see comment).
• OBJECTIVE: Minimize.
• Approx.: Approximable within 1.960 for the case of two non-zero rates. Approximable within 3.802 for the case of unbounded number of rates [72]. For the case of three non-zero rates, the problem admits an 1.522 approximation algorithm [89] [41].
• Hardness: NP-hard to approximate within 96/95 [36].
• Comment: ${r_0=0<r_1<r_2<...<r_N}$ are the distinct rates. For $i=1,\ldots , N$ , $S_i$ denotes the set of all nodes with rate $r_i$ . The cost of an edge in the solution tree $T$ is $c(e)=l(e)r_e$ , where $r_e$ (rate of edge $e$ )is the maximum rate in the component $T-{e}$