Approximation Algorithms for Multicast Routings in a Network with Multi-Sources(<Special Section>Discrete Mathematics and Its Applications)

概要

論文の詳細を見る
We consider the capacitated multi-source multicast tree routing problem (CMMTR) in an undirected graph G=(V,E) with a vertex set V, an edge set E and an edge weight w(e)≥0, e∈E. We are given a source set S⊆V with a weight g(e)≥0, e∈S, a terminal set M⊆V-S with a demand function q: M→R^+, and a real number k>0, where g(s) means the cost for opening a vertex s∈S as a source in a multicast tree. Then the CMMTR asks to find a subset S'⊆S, a partition {Z_1,Z_2,…,Z_l} of M, and a set of subtrees T_1,T_2,…,T_l of G such that, for each i, Σ_<t∈Z_i>q(t)≥k and T_i spans Z_i∪{s} for some s∈S'. The objective is to minimize the sum of the opening cost of S' and the constructing cost of {T_i}, i.e., Σ_<s∈S'>g(s)+Σ^l_<i=1>w(T_i), where w(T_i) denotes the sum of weights of all edges in T_i. In this paper, we propose a (2ρ_<UFL>+ρ_<ST>)-approximation algorithm to the CMMTR, where ρ_<UFL> and ρ_<ST> are any approximation ratios achievable for the uncapacitated facility location and the Steiner tree problems, respectively. When all terminals have unit demands, we give a ((3/2)ρ_<UFL>+(4/3)ρ_<ST>)-approximation algorithm.
社団法人電子情報通信学会の論文
2007-05-01