id: 02190545
dt: j
an: 02190545
au: Karpinski, Marek; Măndoiu, Ion I.; Olshevsky, Alexander; Zelikovsky,
    Alexander
ti: Improved approximation algorithms for the quality of service multicast tree
    problem.
so: Algorithmica 42, No. 2, 109-120 (2005).
py: 2005
pu: Springer-Verlag New York Inc., New York
la: EN
cc: 
ut: Steiner tree problem; multimedia multicast; network design
ci: 
li: doi:10.1007/s00453-004-1133-y
ab: Summary: The Quality of Service Multicast Tree Problem is a generalization
    of the Steiner tree 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 source to non-zero rate nodes is $l\cdot
    r_{e}$, where $r_{e}$ is the maximum node 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 non-zero rates and $4.212$
    for the case of an unbounded number of rates. In this paper we give
    improved 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 known
    approximation ratios of $2.667$ for two non-zero rates and $5.542$ for
    an unbounded number of rates are reduced to $2.414$ and $4.311$,
    respectively.
rv: